The statement you give is true, but it has simple and somewhat more complicated aspects. One has $p_M=c_M$ if and only if $\deg(p_M)=n$ (provided one defines $c_M$ so that it is always unitary), due to the Cayley-Hamilton theorem, which also ensures that $\deg(p_M)\leq n$ always. So your claim is that $\deg(p_M)\geq n$ if and only if for some $x$ the first $n$ iterated images by $M$ (starting from $M^0(x)=x$) are linearly independent. But the degree statement says that the first $n$ powers of $M$ are linearly independent in the vector space of matrices, which is certainly a necessary condition for $x$ to exist; therefore the "if" part of your claim is clear.
The "only if" part is a corollary to the existence of the Rational Canonical Form of a matrix, which is a block diagonal matrix similar to the original matrix, and whose blocks are companion matrices for a sequence of nonconstant monic polynomials, each one of which divides the next polynomial (if there is one). The minimal and characteristic polynomials of the RCF of$~M$, which are the same as those of$~M$ itself, are the last (least common multiple) respectively the product of the polynomials, and they are equal only if there is just one polynomial in the list. In that case $M$ is similar to a (single) companion matrix, and the first vector of the basis on which this form is obtained is$~x$ of the question (the other vectors are the images $M^i(x)$ for $i=1,\ldots,n-1$).
To show the second part without using the theory of rational canonical forms, one can prove a more general fact: for all $M$ there is a vector $x$ so that a polynomial in $M$ annihilates $x$ only of it annihilates the whole space. This requires a bit of polynomial arithmetic. The only way I know to prove that involves decomposing $p_M$ into powers of irreducible polynomials, and the space into a direct sum of subspaces $V_i$ that are annihilated by those powers of irreducibles, evaluated in $M$. Assume for now that this is indeed a direct sum decomposition of the whole space. All $V_i$ are stable under $M$, and therefore under polynomials in $M$. If $p_i$ is the irreducible factor for $V_i$, and $m_i$ its multiplicity in $p_M$, then $p_i^{m_i-1}[M]$ will not annihilate all of $V_i$: otherwise multiplying $p_i^{m_i-1}$ by the other powers of irreducibles would give a polynomial of degree less than that of $p_M$ that would kill all the factors $V_i$, and therefore the whole space. So $V_i$ contains vectors $v_i$ not in $\ker(p_i^{m_i-1}[M])$.
The irreducible factor $p_i$ acts in an invertible way on any other $V_j$: if $p_i(M)$ kills some vector $v\in V_j$, the minimal polynomial killing $v$ divides two relatively prime polynomials $p_i$ and $p_j^{m_j}$, so it is $1$, which means that $v=0$. Therefore taking the sum $x$ of the vectors $v_i$ as indicated above, no proper divisor of $p_M$ evaluated in $M$ and applied to $x$ will annihilate all components in the direct sum decomposition. Then $x$ is a vector that is only annihilated by $p_M$ (and its multiples); it is the existence of such a vector that we wanted to show.
It remains to show that the sum of the spaces $V_i$ is direct and fill the whole space. This follows from a well known general result (sometimes referred to as Chinese remainder theorem) that for mutually coprime polynomials, the subspace $W$ annihilated by their product (evaluated in $M$) is the direct sum of those annihilated by the individual polynomials. For completeness here's a proof (you may have seen different ones). The general case follows by induction from the two-factor case. If $P,Q$ are coprime then the kernels $\ker_P,\ker_Q$ of $P[M]$ and $Q[M]$ are certainly contained in $W=\ker((PQ)[M])$, and we have seen that their intersection is the null subspace. Also $P[M](W)\subseteq\ker_Q$, which by the rank-nullity theorem means that $\dim(W)\leq\dim(\ker_P)+\dim(\ker_Q)$, and so necessarily $W=\ker_P\oplus\ker_Q$.
Best Answer
Hint: 1) Show that there is a vector $e$ such that $(e,Ae,A^2e,\dots,A^{n-1}e)$ is a basis (this is another standard exercice).
Write $Be = \sum_{i=0}^{n-1} a_i A^i e$.
2) Show that $B$ and $\sum_{i=0}^{n-1} a_i A^i$ agree on the basis.