Let $A\in M_n(\mathbb{C})$ and $f\in \mathbb{C}[x]$. In this case if $f(AA^*) = 0$ then $f(A^*A) = 0$
Here's my solution: It's enough to prove it for polynomials of degree 1 because $\mathbb{C}$ is algebraically closed. If $f(AA^*) = 0$ then $AA^* = cE$. Then, if $AA^* = (A^*A)^*$, we have $A^*A = \overline{c}E$. But if $c$ is a root, so is $\overline{c}$, then $f(A^*A) = 0$
Is this solution right?
As discussed in the comments, your reasoning is not sound.
One approach that works is to start by noting that $A^*A$ and $AA^*$ have the same eigenvalues. We can do either by proving that $AB$ and $BA$ always have the same non-zero eigenvalues and that $A^*A$ and $AA^*$ have the same rank, or by noting that the eigenvalues of $AA^*$ and $A^*A$ are both the squares of the singular values of $A$. By the spectral theorem, $AA^*$ and $A^*A$ are diagonalizable, which means that the matrices will satisfy $f(X) = 0$ if and only if the zeros of $f(x)$ include this common set of eigenvalues.
A possible solution that avoids the spectral theorem: note that by the symmetry of the problem, it suffices to show that $f(AA^*) = 0 \implies f(A^*A) = 0$.
With that in mind, suppose that $f(x) = \sum_{j}c_jx^j$ is such that $f(AA^*) = 0$. Suppose that $A$ is invertible. Then we have $$ 0 = f(A^*A) = \sum_{j=0}^n c_j(A^*A)^j = c_0 I + \sum_{j=1}^n c_j(A^*A)^j = c_0 I + A^*\left(\sum_{j=1}^n c_j(AA^*)^{j-1}\right)A \implies\\ 0 = c_0A^{-1} + A^*\left(\sum_{j=1}^n c_j(AA^*)^{j-1}\right) \implies\\ 0 = c_0 I + AA^*\left(\sum_{j=1}^n c_j(AA^*)^{j-1}\right) = c_0 I + \sum_{j=1}^n c_j(AA^*)^{j} = f(AA^*). $$ I am not sure how to extend this to the case where $A$ is singular. I suspect that we can do something using the Moore-Penrose pseudinverse $A^+$ in place of $A^{-1}$, but that seems to defeat the purpose of avoiding the spectral theorem.
I also think we could use the fact that the restriction of $A^*A$ to its image is invertible, which seems more in the spirit of the proof.