I just wanted to make sure that the following statement is true:

Let $A$ be a normal matrix with eigenvalues $\lambda_1,...,\lambda_n$ and eigenvectors $v_1,...,v_n$. Then $A^*$ has the same eigenvectors with eigenvalues $\bar{\lambda_1},..,\bar{\lambda_n}$, correct?

Yes. If $Av=\lambda v$ then $(A-\lambda I_n)v=0$ whence, using the inner product $(x,y)=x^*y$: $$0=(v,(A^*-\overline{\lambda}I_n)\underbrace{(A-\lambda I_n)v}_{=0})\stackrel{\mbox{normality}}{=}(v,(A-\lambda I_n)(A^*-\overline{\lambda}I_n)v)$$ $$=((A^*-\overline{\lambda}I_n)v,(A^*-\overline{\lambda}I_n)v)=\|(A^*-\overline{\lambda}I_n)v\|^2.$$ So $(A^*-\overline{\lambda}I_n)v=0$, i.e. $A^*v=\overline{\lambda}v$.
For any matrix, $\ker B=\ker B^*B$. The inclusion $\subseteq$ is clear. Then we usually use that $(x,B^*Bx)=(Bx,Bx)=\|Bx\|^2$ from which the other inclusion follows.
Hence, for $B$ normal, $\ker B=(\ker B^*B=\ker BB^*=)\ker B^*$.
Just apply this to each normal matrix $B=A-\lambda_jI_n$.