Fix $p$, and let $\mathcal{P} = \{0, 1, \ldots, p-1\}$ be the set of residue classes modulo $p$. For every $r \in \mathcal{P}$, let $S_{r} = \{(a, b) \in \mathcal{P} \times \mathcal{P} : a^{2} + b^{5} \equiv r\}$, and let $s_{r} = |S_{r}|$. Our aim is to prove $s_{r} > 0$ for all $r \in \mathcal{P}$.
We will use the well-known fact that for every residue class $r \in \mathcal{P}$ and every positive integer $k$, there are at most $k$ values $x \in \mathcal{P}$ such that $x^{k} \equiv r$.

Lemma. Let $N$ be the number of quadruples $(a, b, c, d) \in \mathcal{P}^{4}$ for which $a^{2} + b^{5} \equiv c^{2} + d^{5}$. Then
$$N = \sum_{r \in \mathcal{P}} s_{r}^{2}$$
and
$$N \leq p(p^{2} + 4p - 4).$$

Proof. (a) For each residue class $r$ there exist exactly $s_{r}$ pairs $(a, b)$ with $a^{2} + b^{5} \equiv r$ and $s_{r}$ pairs $(c, d)$ with $c^{2} + d^{5} \equiv r$. So there are $s_{r}^{2}$ quadruples with $a^{2} + b^{5} \equiv c^{2} + d^{5} \equiv r$. Taking the sum over all $r \in \mathcal{P}$, the statement follows.

(b) Choose an arbitrary pair $(b, d) \in \mathcal{P}$ and look for the possible values of $a, c$.
1. Suppose that $b^{5} \equiv d^{5}$, and let $k$ be the number of such pairs $(b, d)$. The value $b$ can be chosen in $p$ different ways. For $b \equiv 0$ only $d = 0$ has this property; for the nonzero values of $b$ there are at most 5 possible values for $d$. So we have $k \leq 1 + 5(p-1) = 5p - 4$.
The values $a$ and $c$ must satisfy $a^{2} \equiv c^{2}$, so $a \equiv \pm c$, and there are exactly $2p - 1$ such pairs $(a, c)$.
2. Now suppose $b^{5} \not\equiv d^{5}$. In this case $a$ and $c$ must be distinct. By $(a-c)(a+c) = d^{5} - b^{5}$, the value of $a-c$ uniquely determines $a+c$ and thus $a$ and $c$ as well. Hence, there are $p-1$ suitable pairs $(a, c)$.
Thus, for each of the $k$ pairs $(b, d)$ with $b^{5} \equiv d^{5}$ there are $2p - 1$ pairs $(a, c)$, and for each of the other $p^{2} - k$ pairs $(b, d)$ there are $p-1$ pairs $(a, c)$. Hence,
$$N = k(2p - 1) + (p^{2} - k)(p - 1) = p^{2}(p - 1) + kp \leq p^{2}(p - 1) + (5p - 4)p = p(p^{2} + 4p - 4).$$

To prove the statement of the problem, suppose that $S_{r} = \emptyset$ for some $r \in \mathcal{P}$; obviously $r \not\equiv 0$. Let $T = \{x^{10} : x \in \mathcal{P} \setminus \{0\}\}$ be the set of nonzero 10th powers modulo $p$. Since each residue class is the 10th power of at most 10 elements in $\mathcal{P}$, we have $|T| \geq \frac{p-1}{10} \geq 4$ by $p > 100$.
For every $t \in T$, we have $S_{tr} = \emptyset$. Indeed, if $(x, y) \in S_{tr}$ and $t \equiv z^{10}$ then
$$(z^{-5}x)^{2} + (z^{-2}y)^{5} \equiv t^{-1}(x^{2} + y^{5}) \equiv r$$
so $(z^{-5}x, z^{-2}y) \in S_{r}$.
So, there are at least $\frac{p-1}{10} \geq 4$ empty sets among $S_{1}, \ldots, S_{p-1}$, and there are at most $p-4$ nonzero values among $s_{0}, s_{2}, \ldots, s_{p-1}$. Then by the AM-QM inequality we obtain
$$N = \sum_{r \in \mathcal{P} \setminus rT} s_{r}^{2} \geq \frac{1}{p-4}\left(\sum_{r \in \mathcal{P} \setminus rT} s_{r}\right)^{2} = \frac{|\mathcal{P} \times \mathcal{P}|^{2}}{p-4} = \frac{p^{4}}{p-4} > p(p^{2} + 4p - 4),$$
which is impossible by the lemma.

If $5 \nmid p-1$, then all modulo $p$ residue classes are complete fifth powers and the statement is trivial. So assume that $p = 10k + 1$ where $k \geq 10$. Let $g$ be a primitive root modulo $p$.

We will use the following facts:
(F1) If some residue class $x$ is not quadratic then $x^{(p-1)/2} \equiv -1 \pmod{p}$.
(F2) For every integer $d$, as a simple corollary of the summation formula for geometric progressions,
$$\sum_{i=0}^{2k-1} g^{5di} \equiv \begin{cases} 2k & \text{if } 2k \mid d \\ 0 & \text{if } 2k \nmid d \end{cases} \pmod{p}$$

Suppose that, contrary to the statement, some modulo $p$ residue class $r$ cannot be expressed as $a^{2} + b^{5}$. Of course $r \not\equiv 0 \pmod{p}$. By (F1) we have $(r - b^{5})^{(p-1)/2} = (r - b^{5})^{5k} \equiv -1 \pmod{p}$ for all residue classes $b$.
For $t = 1, 2, \ldots, k-1$ consider the sums
$$S(t) = \sum_{i=0}^{2k-1} (r - g^{5i})^{5k} g^{5ti}$$
By the indirect assumption and (F2),
$$S(t) = \sum_{i=0}^{2k-1} (r - (g^{i})^{5})^{5k} g^{5ti} \equiv \sum_{i=0}^{2k-1} (-1) g^{5ti} \equiv -\sum_{i=0}^{2k-1} g^{5ti} \equiv 0 \pmod{p}$$
because $2k$ cannot divide $t$.
On the other hand, by the binomial theorem,
$$\begin{aligned} S(t) &= \sum_{i=0}^{2k-1} \left( \sum_{j=0}^{5k} \binom{5k}{j} r^{5k-j} (-g^{5i})^{j} \right) g^{5ti} \\ &= \sum_{j=0}^{5k} (-1)^{j} \binom{5k}{j} r^{5k-j} \left( \sum_{i=0}^{2k-1} g^{5(j+t)i} \right) \\ &\equiv \sum_{j=0}^{5k} (-1)^{j} \binom{5k}{j} r^{5k-j} \begin{cases} 2k & \text{if } 2k \mid j+t \\ 0 & \text{if } 2k \nmid j+t \end{cases} \pmod{p} \end{aligned}$$
Since $1 \leq j + t < 6k$, the number $2k$ divides $j + t$ only for $j = 2k - t$ and $j = 4k - t$. Hence,
$$\begin{gathered} 0 \equiv S(t) \equiv (-1)^{t} \left( \binom{5k}{2k-t} r^{3k+t} + \binom{5k}{4k-t} r^{k+t} \right) \cdot 2k \pmod{p} \\ \binom{5k}{2k-t} r^{2k} + \binom{5k}{4k-t} \equiv 0 \pmod{p} \end{gathered}$$
Taking this for $t = 1, 2$ and eliminating $r$, we get
$$\begin{aligned} 0 &\equiv \binom{5k}{2k-2} \left( \binom{5k}{2k-1} r^{2k} + \binom{5k}{4k-1} \right ) - \binom{5k}{2k-1} \left( \binom{5k}{2k-2} r^{2k} + \binom{5k}{4k-2} \right ) \\ &= \binom{5k}{2k-2} \binom{5k}{4k-1} - \binom{5k}{2k-1} \binom{5k}{4k-2} \\ &= \frac{(5k)!^{2}}{(2k-1)! (3k+2)! (4k-1)! (k+2)!} \left( (2k-1)(k+2) - (3k+2)(4k-1) \right ) \\ &= \frac{-(5k)!^{2} \cdot 2k(5k+1)}{(2k-1)! (3k+2)! (4k-1)! (k+2)!} \pmod{p} \end{aligned}$$
But in the last expression none of the numbers is divisible by $p = 10k + 1$, a contradiction.