As G.Myerson already noted we must assume $W$ is finite. Then a different approach for the "warmup" is to observe that if $\omega \in W$ is not a positive real then some power $\omega^N$ ($N \geq 1$) has non-positive real part. Therefore $\omega$ is a root of the polynomial $(X^N-\omega^N)(X^N-\overline\omega^N)$ which has only nonnegative coefficients. The product over all $\omega\in W$ gives a nonnegative polynomial of the desired kind. It also gives an upper bound $3^{\left|W\right|}$ on the number of monomials.
If $\{{\rm Im}\log\omega \colon \omega \in W, \omega \neq 0\} \cup \{2\pi\}$ is ${\bf Q}$-linearly independent then a single $N$ will do for all $\omega\in W$, because as $N$ varies the $\left|W\right|$-tuples of angles formed by the $N$-th powers are dense in $({\bf R}/2\pi{\bf Z})^{\left|W\right|}$. In that case a polynomial of degree $2\left|W\right|$ in $X^N$ will do, and we get an upper bound $2\left|W\right|+1$.
For a lower bound, clearly $2$ is enough iff there is some $N$ such that all nonzero elements of $W$ have the same $N$-th power and that power is negative; else we need at least $3$ monomials. If $W$ contains all $n-1$ nontrivial $n$-th roots of unity then we need at least $n$ monomials, because a polynomial $\sum_k a(k) x^k$ is a multiple of $(x^n-1)\big/(x-1)$ iff the $n$ sums $\sum_j a(k_0+nj)$ ($k_0=0,1,2,\ldots,n-1$) are all equal, and at least one of them must be positive if the $a(k)$ are nonnegative and not all zero.