Considering all integers $|m|, |n| \le 3$ we can get the solutions $2 = 1^2 + 1^2$, $5 = 1^2 + 2^2$ and $13 = (-3)^2 + (-2)^2$. Now, let's prove that there is no other prime numbers satisfying the statement. We have
$$p = m^2 + n^2 \Rightarrow p = (m + n)^2 - 2mn \Rightarrow mn = \frac{(m + n)^2 - p}{2},$$
$$m^3 + n^3 - 4 = (m + n)^3 - 3mn(m + n) - 4 = \frac{-(m + n)^3 + 3p(m + n) - 8}{2},$$
$$p \mid m^3 + n^3 - 4 \Rightarrow p \mid (m + n)^3 + 8.$$
Hence, $p \mid m+n+2$ or $p \mid (m+n)^2 - 2(m+n) + 4$, and from last we conclude that $p \mid mn - m - n + 2$, if we set $p > 2$.
In a first case we have:
$$p \mid m + n + 2 \Rightarrow m^2 + n^2 \le |m + n + 2|,$$
i.e.
$$m^2 + n^2 \le m + n + 2 \Rightarrow (2m - 1)^2 + (2n - 1)^2 \le 10 \Rightarrow -1 \le m, n \le 2.$$
$$m^2 + n^2 \le -(m+n+2) \Rightarrow (2m+1)^2 + (2n+1)^2 \le -6,$$
which is a contradiction.
In a second case:
$$p \mid mn - m - n + 2 \Rightarrow m^2 + n^2 \le |mn - m - n + 2|,$$
i.e.
$$m^2 + n^2 \le mn - m - n + 2 \Rightarrow (2m - n + 1)^2 + 3(n + 1)^2 \le 12 \Rightarrow -3 \le m, n \le 1.$$
$$m^2 + n^2 \le -(mn - m - n + 2) \Rightarrow (2m + n - 1)^2 + 3(n - 1/3)^2 \le -20/3,$$
which is a contradiction.