Given prime $p$, for any integer $a$, exist integer $x,y$ such that $p\mid y^2+x^3+a$.

The solutions to problem N8 of the 53rd IMO, as mentioned by Gerry Myerson, do indeed apply to this problem. In fact it can be generalised. For any strictly positive integer $n$ and prime power $q=p^m$, then for any element $r$ of the finite field $F_q$ of size $q$, the equation $$ y^2+x^n=r\qquad{\rm(*)} $$ has solutions for $x,y\in F_q$, so long as $q$ is large enough. I'll show that $q\ge 2n^2-3n+2$ is enough.

In the question above, we have $n=3$ and, using mod-$p$ arithmetic is the same as working in the field of size $p$, so there are solutions whenever $p\ge 11$. This only leaves $p=2,3,5,7$ to be checked by hand.

As the case with $n=1$ is trivial, I'll assume that $n>1$. Also, if $q$ is a power of $2$ then squaring is injective in $F_q$, so (*) has solutions with $x=0$. I will therefore assume that $q$ is odd. Let $N$ be the number of solutions in $F_q$ to $$ a^2+b^n= c^2+d^n.\qquad{\rm(**)} $$

Upper bound for $N$: First, let $k$ be the number of solutions to $b^n=d^n$. There is one solution with $b=d=0$. Then, for each $d\not=0$ there are at most $n$ possibilities for $b$. So, $$ k\le 1+n(q-1). $$ Similarly, replacing $n$ by $2$, there are at most $1+2(q-1)=2q-1$ solutions to $a^2=c^2$. Putting these together, the number of simultaneous solutions in $F_q$ to $a^2=c^2$ and $b^n=d^n$ is at most $(2q-1)k$.

Now looking at each of the $q^2-k$ solutions to $b^n\not=d^n$, we can write (**) as $(a+c)(a-c)=d^n-b^n$. There are at most $q-1$ possibilities for $a-c$, which uniquely determines $a+c$ and, hence, both $a$ and $c$ (this uses the fact that $q$ is odd, so we can divide by $2$ in $F_q$). \begin{align} N&\le(2q-1)k+(q^2-k)(q-1)=q(q^2-q+k)\\ &\le q(q^2+(n-1)q+1-n)\qquad{\rm(1)} \end{align}

Lower bound for $N$: Letting $s_r$ be the number of solutions to $y^2+x^n=r$ in $F_q$, by counting the number of solutions to $a^2+b^n=r=c^2+d^n$ for each $r$, we have $$ N=\sum_{r\in F_q}s_r^2.\qquad{\rm(2)} $$ I'll calculate a lower bound for $N$ in the situation that there exists some $r\in F_q$ for (*) has no solution -- i.e., that $s_r=0$. Letting $(a,b)$ be a solution to $a^2+b^n=r$ and $z=t^{2n}\not=0$ be a $2n$'th power in $F_q$, $$ (at^n)^2+(bt^2)^n=rz, $$ from which we see that $s_{rz}=s_r$. As there are at least $(q-1)/(2n)$ nonzero powers of $2n$ in $F_q$, we get $s_r=0$ for at least $(q-1)/(2n)$ values of $r$. Applying Cauchy-Schwartz to (2), $$ N\ge\frac1{q-(q-1)/2n}\left(\sum_{r\in F_q}s_r\right)^2. $$ However, $\sum s_r$ is just the number of solutions to $a^2+b^n=r$, which is $q^2$. So, $$ N\ge\frac{q^4}{q-(q-1)/2n}\qquad{\rm(3)} $$

Finally, in the situation that (*) has no solution for some $r\in F_q$, we can combine inequalities (1) and (3) to get $$ q(q^2+(n-1)q+1-n)\ge\frac{q^4}{q-(q-1)/2n}. $$ Rearranging, $$ q^3+2(n-1)^2q+n-1\le (2n^2-3n+2)q^2. $$ As the final two term on the left are positive, this gives $q <2n^2-3n+2$.