It is related to this question.
Question. Suppose that $p$ is a prime, $p-1$ is divisible by $q^2$ for some $q$. Is it true that every number modulo $p$ is a sum of two $q$-th powers.
If $q=2$, then (*) is true. Indeed in that case $p\equiv 1 \mod 4$. Take any number $t \mod p$. WLOG we can assume that $t$ is odd (the product of two sums of two squares is a sum of two squares). If $t\equiv 1 \mod 4$, then consider the arithmetic progression $4np+t, n\ge 0$. By Dirichlet, it contains a prime $p'\equiv 1\mod 4$. By Fermat, $p'$ is a sum of two squares, hence $t$ is a sum of two squares modulo $p$. If $p\equiv -1 \mod 4$, then consider the arithmetic progression $8np+t-2p, n\ge 0$. By Dirichlet, it contains a prime number $p'$ of the form $4k+1$ (since $p\equiv 1\mod 4$) and we are done.
That question may be easier than the question cited above. Or it may be a known open problem.
Update Several simplifications of the argument for $q=2$ were proposed. Although the statement is not true when $(p-1)/q^2$ is small, it is true when this quotient is large enough. I think this answers my question almost completely. Thanks to everybody who gave an answer or a comment.