If $A$ has pairwise distinct diagonal elements one can prove the theorem by induction as follows:

1. By block partitioning one can put $A\in T_{n}({\mathbb F})$  to the form
$$ A = \begin{pmatrix} \alpha & a \left(\alpha I - A'\right)\\ 0 & A'\end{pmatrix}$$
with $\alpha \in{\mathbb F}$, $a\in {\mathbb F}^{n-1}$ a _row_ vector and $A'\in T_{n-1}({\mathbb F})$. Here one uses that $\alpha I - A'$ is non singular. For $p \in {\mathbb F}[t]$ one has
$$ p(A) = \begin{pmatrix} p(\alpha) & a \left(p(\alpha) I - p(A')\right)\\ 0 & p(A')\end{pmatrix}.$$
2. For $X \in T_{n}({\mathbb F})$, one has $[A,X]=0$ iff $X$ can be put to the form
$$ X = \begin{pmatrix} \xi & a \left(\xi I - X'\right)\\ 0 & X'\end{pmatrix}$$
with $[A',X']=0$.
3. Now, if $B\in T_{n}({\mathbb F})$ satisfies $[A,X] = 0\Rightarrow [B,X]=0$ it must be (by Step 2) of the form
$$ B = \begin{pmatrix} \beta & a \left(\beta I - B'\right)\\ 0 & B'\end{pmatrix},$$
where $[A',X'] = 0\Rightarrow [B',X']=0$. By induction hypothesis, there is a polynomial $q\in {\mathbb F}[t]$ such that $B'=q(A')$. 
4. Now, if one denotes the pairwise distinct diagonal elements (i.e., eigenvalues) of the upper triangular matrix $A$ by $\alpha, \lambda_1,\ldots,\lambda_{n-1}$ the polynomial $p \in {\mathbb F}[t]$ solving the interpolation problem $p(\alpha)=\beta$ and $p(\lambda_j)=q(\lambda_j)$ ($j=1,\ldots,n-1$)  yields $p(A')=q(A') = B'$ and hence, by Step 1, $p(A)=B$. 

In particular, the thus constructed polynomial $p$ has degree at most $n-1$.