The following sentence by Federico

"Conversely, given f, the matrices at which it vanishes are all those who have eigenvalues equal to the scalar roots of the polynomial, with algebraic multiplicities smaller or equal than their multiplicities as scalar roots of f"

seems to me unclear.

We want to solve the equation (E): $p(X)=0$ - where $p\in K[x]$ - in the unknown $X\in M_n(K)$.

i) $K$ is an algebraic closed field. The roots of $p$ are $(\alpha_i)_{i\leq s}$ with multiplicity $(r_i)_{i\leq s}$. Let $J_r$ be the nilpotent Jordan block of dimension $r$. Then $X$ is a solution of (E) IFF $X$ is similar to $diag(U_1,\cdots,U_k)$ for any choice of $k$ and of the dimension $n_j$ of $U_j$ satisfying $n_1+\cdots+n_k=n$ and for any choice of $U_j$ among the matrices of following forms: $\alpha_i I_{n_j}+J_{n_j}$ with $i\leq s$ and $n_j\leq r_i$.

ii) $K$ is a field not alg. closed. We factor $p$ in irreducible $p=p_1^{r_1}\cdots p_s^{r_s}$. The result is similar to that of i). It suffices to choose $U_j$ among the companion matrices of ${p_i}^{q}$ where $q=n_j/degree(p_i)$ and $q\leq r_i$.

iii) $K$ is an euclidean ring (for example $\mathbb{Z}$). As Matthias wrote, it is much more difficult. We must seek a number of ideal classes ; using Magma software, we can do that but, morover, we must find one representant in each class, that is not obvious. For example, solve $A^3=I_n$ where $A\in M_n(\mathbb{Z})$.

Note that, obviously, this Joseph's question has not research level. Yet everyone rushes to give its answer (me also !). Hilarious detail: "il maestro" Joseph has $43800$ points. Compare with this post sent on MO and on MSE by an unknown user - here $K=\mathbb{Z}[i]$ -
http://math.stackexchange.com/questions/634655/how-to-find-all-the-solutions-to-ia-cdotsan-0
this question (in my opinion) is difficult and interesting. Yet the post was expelled from MO because it had not the research level. Hilarious detail: this poor unknown user has only $91$ points. La Fontaine, a great French poet (not the same as the poet of Michael Connelly), wrote (in french) "Selon que vous serez puissant ou misérable,
Les jugements de cour vous rendront blanc ou noir", that is (in my bad non idiomatic English) "Depending on whether you will be powerful or miserable,
Court judgments make you white or black".

Matrix Polynomials; Higham,Functions of matrices. – Federico Poloni Jun 15 at 7:22