I am considering how to provide an alternative proof of the lemma used in the proof that $\Phi_n$ is irreducible:
Lemma: If $\Phi_n=f_1 f_2\cdots f_r$ is a factorization into monic irreducible polynomials in $\mathbb Q[X]$ then if $\zeta$ is a root of $f_1$ and $p\nmid n$ is a prime number then $\zeta^p$ is a root of $f_1$ as well.
Remark
I will use the following statement that is easily proven:
Consider a field extension of the form $K(\alpha)\supset K$ for some $\alpha$ algebraic over $K$. Then if $f$ is monic and irreducible with $f(\alpha)=0$ it follows that $f=\mbox{Irr}(\alpha,K)$.
My version of the lemma
Lemma: If $\Phi_n=f_1f_2\cdots f_r$ is a factorization into monic irreducible polynomials in $\mathbb Q[X]$ and add to this that $\deg(f_1)\leq\deg(f_2)\leq...\leq\deg(f_r)$, then if $\zeta$ is a root of $f_1$ and $p\nmid n$ is a prime number then $\zeta^p$ is a root of $f_1$ as well.
Analysis: Let $\zeta$ be a root of $f_1$. Then $\mbox{Irr}(\zeta,\mathbb Q)=f_1$. Since $p\nmid n$ we see that both $\zeta$ and $\zeta^p$ are roots of $\Phi_n$. In particular $\zeta^p$ must be a root of some $f_q$. Now since $\zeta^p\in\mathbb Q(\zeta)$ we see that we have a tower of fields $$ \mathbb Q(\zeta)\supset\mathbb Q(\zeta^p)\supset\mathbb Q $$ Since $f_1$ was defined to have minimal degree among the $f_i's$ we see on one hand that $f_q$ must have degree greater than or equal to $f_1$. On the other hand, since $f_q$ is the defining polynomial for $\zeta^p$ over $\mathbb Q$, looking on the tower of fields above it must have degree less than or equal to $f_1$. It follows that $$ \deg(f_q)=\deg(f_1) $$ Thus $\mathbb Q(\zeta)=\mathbb Q(\zeta^p)$.
Now iterating like in the original proof combining different prime powers of $\zeta$ this argument can be repeated to see that each $\zeta^k$ with $\gcd(k,n)=1$ will be a root of some $f_i$ of the same degree as $f_1$. So all the $f_i$'s have the same degree. Furthermore $$ \mathbb Q(\zeta)=\mathbb Q(\zeta^k) $$ for all $k$ relatively prime to $n$.
But then I do not know where this takes us...
After modification, your argument succesfully estabishes that all individual primitive $n$-th roots of unity generate the same field over$\def\Q{\Bbb Q}~\Q$, and therefore have minimal polynomials of the same degree. The same is true over larger fields than$~\Q$, where $\Phi_n$ does factor (into equal degree factors), so you have no hope of going from here to the conclusion you seek.
In fact what you have proved is clear from purely group theoretic argments: every primitive $n$-th root of unity generates the group of all $n$-th roots of unity, so for every pair of primitive $n$-th roots of unity, each one can be written as a power of the other, so the two must generate the same field. In fact the proof you gave could be done directly for $k$ relatively prime to $n$ in place of$~p$, as you never use primality. You do of course need that fact (an also that the irredicible factors of$~\Phi_n$ have integer coefficients, in othe words that you are working over$~\Q$) in order to complete the proof by reducing to polynomials over $\Bbb F_p$ and using the Frobenius automorphism, as is done in the classical proof by Dedekind/van der Waerden (not Gauss, who only did the case where $n$ is prime).