I don't have an answer, but I do have an example, and a few thoughts.
The problem is to find nonconstant $f$ in ${\bf C}[x]$ such that $f:M_n({\bf C})\to M_n({\bf C})$ is not onto.
Let's observe that for any nonconstant $f$ and any diagonal matrix $D$ there is a diagonal matrix $D'$ such that $f(D')=D$, simply because (as @Martin notes in the comments) every nonconstant polynomial is onto as a map from $\bf C$ to (shining) $\bf C$.
If $A$ is diagonalizable, say, $P^{-1}AP=D$ is diagonal, then find $D'$ such that $f(D')=D$, and you get $f(PD'P^{-1})=A$. This shows that if there's anything not in the range of $f$, it must be nondiagonalizable.
With that as motivating preamble, here's an example. I say $f(x)=x^2$ is "broken", because there's no matrix $N$ such that $N^2=M$, when $M=\pmatrix{0&1\cr0&0\cr}$
There's probably a conceptual proof of this, based on consideration of eigenspaces and such, but here's a brute force proof. If $N=\pmatrix{a&b\cr c&d\cr}$ then $N^2=\pmatrix{a^2+bc&(a+d)b\cr(a+d)c&bc+d^2\cr}$ So $N^2=M$ amounts to $a^2+bc=0;\quad(a+d)b=1;\quad(a+d)c=0;\quad bc+d^2=0$ The 3rd equation says $a+d=0$ or $c=0$; the second says $a+d\ne0$, hence, $c=0$. Then the first and fourth say $a=d=0$, and the second is impossible.