As Geoff Robinson says, a Jordan form takes you quite far. Evaluating a scalar polynomial (or an analytic function) $f(x)$ at a Jordan block $J_{\lambda,t}$ of size $t$ and eigenvalue $\lambda$ gives the triangular Toeplitz matrix
$$
f(J_{\lambda,t})=
\begin{bmatrix}
f(\lambda) & f'(\lambda) & f''(\lambda) & \dots & f^{t-1}(\lambda)\\
0 & f(\lambda) & f'(\lambda) & \ddots & \vdots\\
0 & 0 & \ddots & \ddots & \vdots \\
0 & 0 & \dots & 0 & f(\lambda)
\end{bmatrix}.
$$
So evaluating $f(A)$ where $A$ has Jordan form $A=M (\bigoplus J_{\lambda_i,t_i}) M^{-1}$ gives $M(\bigoplus f(J_{\lambda_i,t_i}))M^{-1}$.

In other words, for $f(A)$ to be zero, $f$ needs to satisfy $f(\lambda)=0,f'(\lambda)=0,f''(\lambda)=0,\dots,f^{(t-1)}(\lambda)=0$, for each eigenvalue $\lambda$ of $A$ with algebraic multiplicity $t$. 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$. This is just a complicated way to state that $f$ has to be a multiple of the minimal polynomial of $A$ (which sounds quite obvious).

This solves completely your first example; as for the second, it doesn't quite fit your definition, as has been pointed out in the comments.


A reference for the computation of $f(J_{\lambda,t})$, and other equivalent definitions of functions evaluated at a matrix argument, is Chapter 1 of Higham, *Functions of matrices*.