For every prime $k = -1 \mod 4$, and every primitive root $a$ modulo $p$, the polynomials $P(x) = 1 + x^{a^2} + x^{a^4} + ... + x^{a^{k-1}}$ and $Q(x) = 1 + x^a + x^{a^3}+\cdots+ x^{a^{k-2}}$ are magicals
(of course, reduce the exponents modulo $k$ in order to make the degrees of the polynomials $<k$).
Indeed, it is easy to see that $\overline{P(\omega)} = Q(\omega)$ (because the conjugation sends $\omega$ to $\omega^{-1}=\omega^{a^{\frac{k-1}{2}}}$).
Every automorphism of the galois group of ${\mathbb Q}(\omega)/{\mathbb Q}$ sends
$\omega$ (a primitive element of the extension) to $w^{a^i}$ for some $i$.
So, the expression $|P(\omega)|^2=P(\omega)Q(\omega)$ is fixed by the Galois group, hence belongs to $\mathbb Q$.
Therefore, $|P(\omega)|^2\in {\mathbb Q} \cap Z[\omega] = Z$ because $Z$ is integrally closed (a consequence, say, of the symmetric functions theorem).
Thus $|P(\omega)|^2 \in \mathbb N$ and $|Q(\omega)|^2\in \mathbb N$, as desired.
Next, for every prime $k = 5 \mod 8$, and every primitive root $a$ modulo $p$, the polynomials
$P_1(x) = 1 + x^{a} + x^{a^5} + x^{a^9} + \cdots$,
$Q_1(x) = 1 + x^{a^2} + x^{a^{6}} + x^{a^{10}} + \cdots $,
and
$P_2(x) = 1 + x^{a^3} + x^{a^7} + x^{a^{11}} + \cdots$
$Q_2(x) = 1 + x^{a^4} + x^{a^8} + x^{a^{12}} + \cdots $,
are (not checked very carefully) magicals.
You have to use the pigeon hole principle to show first that $P_1P_2(\omega) = Q_1Q_2(\omega)$ (let me leave this point, this may be wrong for every $p=5\mod 8$, even if it is true for some primes like p=13).
Once this is done, it is easily seen that the complex conjugation sends
$P_1(\omega)$ to $P_2(\omega)$, and $Q_1(\omega)$ to $Q_2(\omega)$. The generator $\omega\to \omega^a$ of the cyclic Galois group sends $P_1$ to $Q_1$ and $P_2$ to $Q_2$. Hence $P_1P_2$ and $Q_1Q_2$ are fixed by the Galois group, and the conclusion follows as previously.
These cases cover the given examples.