I think I have the proof to this problem, but I'm not sure if it's correct:
Let $r$ be a primitive root of the odd prime $p$, and let $d=\gcd(k,p-1)$. Prove that the values of $a$ for which the congruence $x^k\equiv a\pmod{p}$ is solvable are $r^d,r^{2d},r^{3d},\dots,r^{[(p-1)/d]d}$.
I also use this theorem in my proof:
Theorem 8.12 Corollary
Let $p$ be a prime and $\gcd(a,p)=1$. Then the congruence $x^k\equiv a\pmod{p}$ has a solution if and only if $a^{(p-1)/d}\equiv 1\pmod{p}$, where $d=\gcd(k,p-1)$.
Proof:
By Theorem 8.12 Corollary, $x^k\equiv a\pmod{p}$ has a solution $\iff$ $a^{(p-1)/d}\equiv 1\pmod{p}$.
Consider $a=r^{td}$, some $t\in\mathbb{Z}, 0<t\leq(p-1)/d$.
Then, $(r^{td})^{(p-1)/d}=r^{t(p-1)}=(r^{p-1})^t\equiv 1^t\equiv 1\pmod{p}$, by Fermat's Little Theorem.
Note also that for some $(p-1)/d<s\in\mathbb{Z}$, $r^{sd}\equiv r^{td}$ for some $0<t\leq(p-1)/d$ since $r^{sd}=r^{[t+(p-1)/d]d}=r^{td}r^{p-1}\equiv r^{td}\cdot 1\equiv r^{td}\pmod{p}$ by Fermat's Little Theorem.
Thus, the values of $a$ for which $x^k\equiv a\pmod{p}$ is solvable are $r^d,r^{2d},r^{3d},\dots,r^{[(p-1)/d]d}$. $\blacksquare$
Still, I'm not sure how to prove that there are no other $a$'s for which the congruence is solvable...