Note that
$$\sum_{1 \le x_i \le p-1} \left(1 - \left(x_1^4 + x_2^4 + x_3^4 + x_4^4\right)^{p-1}\right) \stackrel{p}{=} \qquad (p-1)^4 - (p-1)^4 \overbrace{\left(\sum_{\substack{\frac{p-1}{4}|\theta_i; \\ \sum \theta_i = p-1}}^A \begin{pmatrix} p-1 \\ \theta_1, \theta_2, \theta_3, \theta_4 \end{pmatrix}\right)}^{p}.$$

$$\begin{align*} A \stackrel{p}{=} & 4 \binom{p-1}{p-1} + 12 \binom{p-1}{\frac{p-1}{4}, 3\frac{p-1}{4}} + 12 \binom{p-1}{\frac{p-1}{4}, \frac{p-1}{4}, \frac{p-1}{2}} + \binom{p-1}{\frac{p-1}{4}, \frac{p-1}{4}, \frac{p-1}{4}, \frac{p-1}{4}} \\ \stackrel{p}{=} & 4 + \frac{12(p-1)!}{\left(\frac{p-1}{4}\right)!\left(\frac{3(p-1)}{4}\right)!} + \frac{6(p-1)!}{\left(\frac{p-1}{2}\right)!^2} + \frac{12(p-1)!}{\left(\frac{p-1}{2}\right)!(\frac{p-1}{4})!^2} + \frac{(p-1)!}{\left(\frac{p-1}{4}\right)!^4} \\ \stackrel{p}{=} & 4 + \frac{12(p-1)!}{(-1)^{\frac{p-1}{4}}(p-1)!} + \frac{6(p-1)!}{-1} + \frac{12(p-1)!}{\left(\frac{p-1}{2}\right)!(\frac{p-1}{4})!^2} + \frac{(p-1)!}{\left(\frac{p-1}{4}\right)!^4} \\ \stackrel{p}{=} & 4 - 12 + 6 + 12 \frac{\left(\frac{p-1}{2}\right)!}{\left(\frac{p-1}{4}\right)!^2} + \frac{-1}{\left(\frac{p-1}{4}\right)!^2}. \end{align*}$$
$$$$

If $a \stackrel{p}{\equiv} (\frac{p-1}{2})!$ and $b \stackrel{p}{\equiv} \frac{1}{(\frac{p-1}{4})!^2}$, then $A \stackrel{p}{\equiv} -2 + 12ab - b^2$; therefore,
$$-A + 1 \stackrel{p}{\equiv} b^2 - 12ab + 3 \stackrel{p}{\equiv} (b - 6a)^2 - 36a^2 + 3 \stackrel{p}{\equiv} (b - 6a)^2 + 39.$$
And according to the assumption, $\left(\frac{-39}{p}\right) = -1$, which completes the proof.