$\def\ZZ{\mathbb{Z}}$ $\def\RR{\mathbb{R}}$ $\def\QQ{\mathbb{Q}}$ $\def\Re{\mathrm{Re}}$ $\def\Im{\mathrm{Im}}$Let $|W|=n$. I will show that $2n+1$ monomials are always sufficient, and are generically necessary. (Noam Elkies has already shown that $2n+1$ is generically sufficient.) If $W$ is closed under complex conjugation and has no real points, then this argument shows that $n+1$ is enough, since we could replace $W$ by $W' := \{ \omega \in W : \Im(\omega) > 0 \}$ and any real polynomial which vanishes on $W'$ will also vanish on $W$.
Let the elements of $W$ be $\omega_j = x_j + i y_j = r_j e^{i \theta_j}$. For any nonnegative integer $m$, let $v_m$ be the vector
$$v_m := (\Re(\omega_1^m), \Im(\omega_1^m), \ldots, \Re(\omega_n^{m}), \Im(\omega_n^{m}))$$
So the $v_i$ are vectors in $\RR^{2n}$, and our goal is to find a positive linear relation between them.
Generic necessity: Suppose that we had a linear relation $\sum a_i v_{m_i}=0$ using only $2n$ terms. Then the vectors $v_{m_1}$, ..., $v_{m_{2n}}$ would be linearly dependent, so the $2n \times 2n$ matrix they form would have determinant zero. This is a nontrivial polynomial relation between the $x_j$ and $y_j$ with integer coefficients. If the $\omega_j$ are chosen generically then the $x_j$ and $y_j$ will be algebraically independent over $\QQ$, and no such relation will exist.
Sufficiency: This is essentially Noam's proof when the $\theta_j$'s are linearly independent over $\mathbb{Q}$, but with a lot more checking of degenerate cases.
Suppose, for the sake of contradiction, that we cannot write $0$ as $\sum_{i=1}^{2n+1} a_i v_{m_i}$ with the $a_i \geq 0$ and not all $0$.
Equivalently, assume that, for any $(2n+1)$-tuple of vectors of the form $v_m$, the origin is not in the convex hull of the tuple.
By the contrapositive of Carathéodory's theorem, we conclude that $0$ is not in the convex hull of the vectors $v_m$. Let $K$ be the closure of the convex hull of the $v$'s.
We conclude that $0$ is not in the interior of $K$.
By Farkas's lemma, there is a linear function $\lambda : \RR^{2n} \to \RR$ with is $\geq 0$ on $K$ and not identically $0$ on $K$.
Equivalently, $\lambda(v_m)$ is nonnegative for all $m$ and is positive for some $m$.
We can write $\lambda$ in the form
$$(f_1, g_1, f_2, g_2, \ldots, f_n, g_n) \mapsto \Re \left( \sum (a_j+i b_j) (f_j+i g_j) \right)$$
for some $a_j$ and $b_j$. Set $\zeta_j = a_j+i b_j$. Our hypothesis now is that
$$\phi(m) : = \Re \left( \sum_j \zeta_j \omega_j^m \right)$$
is nonnegative for all $m$ and positive for some $m$; our goal is to deduce a contradiction.
Let $R$ be the set of distinct values of $|\omega_j|$, and let the elements of $R$ be $r_1 > r_2 > \cdots > r_p$.
Let the elements of $R$ with norm $r_j$ be $r_j \exp(i \theta^j_1)$, $r_j \exp(i \theta^j_2)$, ..., $r_j \exp(i \theta^j_{k(j)})$.
Reindex the $\zeta$'s accordingly as $\zeta^1_1$, $\zeta^1_2$, ...., $\zeta^1_{k(1)}$, .... $\zeta^p_1$, ...., $\zeta^p_{k(p)}$.
Put
$$\phi_j(m) := \Re \left( \sum_{\ell=1}^{k(j)} \zeta^j_{\ell} \exp(i m \theta^j_{\ell}) \right)$$
so
$$\phi(m) = \sum_j r_j^m \phi_j(m). \quad (\ast)$$
Since $\phi(m)$ is not identically zero, not all of the $\phi_j(m)$ are identically zero. Let $j_0$ be minimal such that $\phi_{j_0}(m)$ takes nonzero values.
Lemma There is $c>0$ so that $\phi_{j_0}(m)$ is infinitely often less than $-c$.
Proof By assumption, $\phi_{j_0}$ is not identically zero. Since none of the $\theta$'s are $0 \bmod 2 \pi \ZZ$, the Cesaro limit $\lim_{M \to \infty} \frac{1}{M} \sum_{1 \leq m \leq M} \phi_{j_0}(m)$ is $0$. (This is where we use that the $\omega$'s are not positive reals. Note that this is true even if some of the $\theta$'s are in $2 \pi \QQ$.) So $\phi_{j_0}$ is negative for some $m$, say $m_0$. Let $\phi_{j_0}(m_0)=-2c$.
Consider any $\delta>0$. By a basic pigeonhole argument, we can find infinitely many $N$ such that $| N \theta^{j_0}_{\ell} \bmod 2 \pi \ZZ| < \delta$. (Note that this is true even if the $\theta$'s are not linearly independent over $\QQ$.) Choosing $\delta$ small enough, for such $N$'s, we have $\phi_{j_0}(m_0+N) < -c$. $\square$.
Therefore, there are infinitely many $m$ for which the leading term of $(\ast)$ is as negative as $-c r_{j_0}^m$, and all the other terms are exponentially less. Thus, we have found an $m$ for which $\phi(m)<0$. This is a contradiction and the theorem follows.
Remark: Carathéodory + Farkas + (something clever) is a general proof technique.
Chapter 2 of Barvinok's A Course in Convexity has many nontrivial exercises of this form.
