Nice problem! Clearly, $p > k$. Answer: $k=1,2,3,4$. General claim (gc): according to Thue's lemma, there exists positive integers $x,y$ such a $p|x^2+ky^2$ and $x^2+ky^2<(k+1)p$. Case $k=1$: in this case $p^2=x^2+y^2$ and so $p \equiv_4 1$ and it's good by Fermat's christmas theorem or $p \equiv_4 3$. In second case it is impossible since by well-known fact $p | x,y \Rightarrow x^2+y^2 \geq 2p^2>p^2$. So, $k=1$ works. By analogue, $k=4$ works. Case $k=2$: by gc there are $x,y \in \mathbb{Z_+}$ such a $x^2+2y^2=2p$ or $x^2+2y^2=p$. If $x^2+2y^2=2p$ then $2|x$ and $x=2a \Rightarrow p=2a^2+y^2$. So, $k=2$ works. Case $k=3$: doesn't works because if $p=2$ we get $2^2=1^2+3 \cdot 1^2$, but $2 \not = x^2+3y^2$ Case $k=5$: we get that for $p=7$ it doesn't works: $7^2=2^2+5 \cdot 3^2$, but, of course, $7 \not = x^2+5y^2$. Case $k=6$: we get that for $p=5$ it doesn't works: $5^2=1^2+6 \cdot 2^2$, but $5 \not = x^2+6y^2$.

@above $k=3$ doesn't work because of $a=1, b=1, p=2$

GeorgeRP wrote: @above $k=3$ doesn't work because of $a=1, b=1, p=2$ Thank you! I forgot case $p=2$.