Can commuting matrices $X,Y$ always be written as polynomials of some matrix $A$?
As promised I will answer my own question. The answer is negative, it can happen that $X$ and $Y$ cannot be written as polynomials of any one matrix $A\in M_n(K)$.
Following the comment by Martin Brandenburg, this can even happen when $X$ and $Y$ are both diagonal, if the field $K$ is too small. Indeed if $K$ is a finite field of $q$ elements then for any diagonalisable matrix $A$ one has $\dim K[A]\leq q$ because $q$ limits the degree of split polynomials without multiple roots, and the minimal polynomial of $A$ must be of this kind. This means that when $n>q$ the dimension $n$ of the subalgebra $D$ of all diagonal matrices is too large for it to be of the form $K[A]$ for one of its members. And as long as $n\leq q^2$ one can find diagonal matrices $X,Y$ that generate all of $D$, while ensuring that all matrices$~A$ commuting with both $X$ and $Y$ must be diagonal; this excludes finding such $A$ with $X,Y\in K[A]$. Indeed one can arbitrarily label each of the $n$ standard basis vectors with distinct elements of $K\times K$, and define $X,Y$ so that each such basis vector is a common eigenvector, with respective eigenvalues given by the two components of the label; one then easily realises each projection on the $1$-dimensional space generated by one of the standard basis vectors as a polynomial in $X,Y$, forcing any matrix commuting with both $X$ and $Y$ (and therefore with these projections) to be diagonal.
But for examples valid in arbitrary field, it is better to focus attention on nilpotent matrices, avoiding the "regular" ones with minimal polynomial $X^n$ (and hence with a single Jordan block). The counterexample that I had in mind was the pair of $4\times4$ matrices each of Jordan type $(2,2)$: $$ X=\begin{pmatrix}0&1&0&0\\0&0&0&0\\0&0&0&1\\0&0&0&0\end{pmatrix} ,\qquad Y=\begin{pmatrix}0&0&1&0\\0&0&0&1\\0&0&0&0\\0&0&0&0\end{pmatrix} ,\qquad \text{which have } XY=YX=\begin{pmatrix}0&0&0&1\\0&0&0&0\\0&0&0&0\\0&0&0&0\end{pmatrix} $$ while $X^2=Y^2=0$. Then the algebra $K[X,Y]$ has dimension $4$, and is contained in the subalgebra of upper triangular matrices $A$ with identical diagonal entries and also $A_{2,3}=0$. For any $A$ in this subalgebra, and therefore in particular for $A\in K[X,Y]$, one has $\dim K[A]\leq3$, since $(A-\lambda I)^3=0$ where $\lambda$ is the common diagonal entry of $A$; in particular $K[A]\not\supseteq K[X,Y]$ for such$~A$. But one also has $\dim K[A]\leq4$ for any $A\in M_4(K)$, and this shows that one cannot have $K[A]\supseteq K[X,Y]$ unless $A\in K[X,Y]$, and one therefore cannot have it at all.
The answer in the MO thread indicated in the other answer indicates that there are counterexamples even for $n=3$; indeed it suffices to strip either the first row and column or the last row and column off the matrices $X,Y$ given above. The argument is similar but even simpler for them. The resulting matrices generate the full subalgebra of matrices of the form
$$
\begin{pmatrix}\lambda&a&b\\0&\lambda&0\\0&0&\lambda \end{pmatrix}
\quad \text{respectively of those of form}\quad
\begin{pmatrix}\lambda&0&b\\0&\lambda&a\\0&0&\lambda \end{pmatrix};
$$
having dimension $3$ it can only be contained in $K[A]$ if $A$ is in the subalgebra, but then the minimal polynomial of $A$ has degree at most $2$ so the algebra it generates cannot be all of that subalgebra.
These two subalgebras are analogues of the commutative subalgebra of dimension${}>n$ that I mentioned in the question, but for the case $n=3$ where its dimension is only equal to $n$. If had bothered to look at this more modest case rather than go directly for the "excessive" subalgebra for $n\geq4$ right away, then I might have found this example myself; I guess one should never neglect the small cases.
The answer is given in the accepted answer of MO/34314. Don't klick when you want to keep the suspense.