As what you observed, when , then everything is a cube mod p. [This is so because x|-> x^3 is an automorphism of Z/pZ] To have a solution for y, you need (x^3/p) = (x/p) = 1 where (* / p) is the legendre symbol. Anyways, if p is 2 mod 3, then you can always find (x, y) such that p|y^2 – x^3. I am not sure whether you can actually determine the actual form of (x, y), the best you can do is to further consider primes mod 4, and use quadratic reciprocity, but I am not sure how helpful that is. If p is 1 mod 3, then exactly one third of {1, 2, …, p-1} is a cube. Then it is possible that y^2 = x^3 + pk has no solution. i.e. this happens exactly when all the cubes x satisfy (x/p) = -1. And then you are now back to teh same dilemma.

Also, the equation you are interested in. namely y^2 = x^3 + pk, is studided intensively by mordell in his book: “diophantine equations”, you may want to look into that. Actually, he studided y^2 = x^3 + a, for various a.