Let $a$ and $b$ be two distinct natural numbers. It is known that $a^2+b|b^2+a$ and that $b^2+a$ is a power of a prime number. Determine the possible values of $a$ and $b$.
1. According to the given information, \(a \neq b\) are two natural numbers and there is a prime \(p\) and a natural number \(k\) satisfying:
   \[
   a^2 + b \mid b^2 + a
   \]
   and
   \[
   b^2 + a = p^k.
   \]

2. Combining these conditions, we obtain:
   \[
   a^2 + b \mid p^k,
   \]
   implying there is a natural number \(m \leq k\) such that:
   \[
   a^2 + b = p^m.
   \]

3. Subtracting the equation \(a^2 + b = p^m\) from \(b^2 + a = p^k\), we get:
   \[
   (b - a)(b + a - 1) = p^m(p^{k-m} - 1).
   \]

4. From the above equation, we infer \(a < b\) and \(m < k\).

5. Assume \(p^m \mid b - a\) or \(p^m \mid b + a - 1\). Consequently, since \(b + a - 1 > b - a\), we have:
   \[
   p^m \leq b + a - 1,
   \]
   which according to \(a^2 + b = p^m\) yields:
   \[
   b + a - 1 \geq a^2 + b,
   \]
   i.e.,
   \[
   a^2 - a + 1 \leq 0,
   \]
   which is impossible since \(a \geq 1\). This contradiction combined with the equation \((b - a)(b + a - 1) = p^m(p^{k-m} - 1)\) gives us:
   \[
   p \mid b - a,
   \]
   and
   \[
   p \mid b + a - 1.
   \]

6. Subtracting and adding these two results, we obtain:
   \[
   p \mid 2a - 1,
   \]
   and
   \[
   p \mid 2b - 1.
   \]
   Hence, \(p\) is odd, which according to \(b^2 + a = p^k\) gives us:
   \[
   0 \equiv 4p^k = (2b)^2 + 2 \cdot (2a) \equiv 1^2 + 2 \cdot 1 = 1 + 2 = 3 \pmod{p},
   \]
   i.e.,
   \[
   3 \mid p.
   \]
   Therefore, \(p = 3\).

7. Substituting \(p = 3\) into the equations, we get:
   \[
   b^2 + a = 3^k,
   \]
   and
   \[
   a^2 + b = 3^m.
   \]

8. Observe that \(3^k = b^2 + a \geq 2^2 + 1 = 4 + 1 = 5 > 3\), yielding \(k \geq 2\).

9. Next, assume \(9 \mid b - a\) and \(9 \mid b + a - 1\). Hence, \(9 \mid (b + a - 1) \pm (b - a)\), which means \(9 \mid 2a - 1\) and \(9 \mid 2b - 1\). Thus, we have \(a \equiv b \equiv 5 \pmod{9}\), which according to \(b^2 + a = 3^k\) (since \(k \geq 2\)) yields:
   \[
   0 \equiv 3^k = b^2 + a \equiv 5^2 + 5 = 25 + 5 = 30 \equiv 3 \pmod{9},
   \]
   a contradiction implying \(9 \nmid b - a\) or \(9 \nmid b + a - 1\). Hence, by the equation \((b - a)(b + a - 1) = 3^m(3^{k-m} - 1)\), we obtain:
   \[
   3^{m-1} \mid b - a,
   \]
   or
   \[
   3^{m-1} \mid b + a - 1.
   \]

10. Thus, there are two natural numbers \(s\) and \(t\) such that:
   \[
   b - a = 3^{m-1}s,
   \]
   or
   \[
   b + a - 1 = 3^{m-1}t,
   \]
   where \(s, t \in \{1, 2\}\) (we know that \(b - a < b + a - 1 < p^m = 3^m\)).

11. **Case 1:** \(b - a = 3^{m-1}s\). If \(s = 2\), then \(b - a\) is even, yielding \(a^2 + b\) is even, contradicting \(a^2 + b = 3^m\). Consequently, \(s = 1\), which gives us \(b - a = 3^{m-1}\), which combined with \(a^2 + b = 3^m\) yields:
   \[
   3(b - a) = 3^m = a^2 + b.
   \]
   This means:
   \[
   2b = a^2 + 3a,
   \]
   which according to \(a^2 + b = 3^m\) results in:
   \[
   2 \cdot 3^m = 2a^2 + 2b = 2a^2 + (a^2 + 3a) = 3a(a + 1),
   \]
   i.e.,
   \[
   a(a + 1) = 2 \cdot 3^{m-1}.
   \]
   Therefore, since \(\gcd(a, a + 1) = 1\), we have \(3^{m-1} \mid a\) or \(3^{m-1} \mid a + 1\), which combined with \(a(a + 1) = 2 \cdot 3^{m-1}\) yields \(a \leq 2\). Thus, we obtain \(3^{m-1} = 1\) when \(a = 1\) and \(3^{m-1} = 3\) when \(a = 2\). In other words, since \(2b = a^2 + 3a\), we obtain \((a, b, m) = (1, 2, 1)\) or \((a, b, m) = (2, 5, 2)\), yielding \(b^2 + a = 2^2 + 1 = 4 + 1 = 5\) and \(b^2 + a = 5^2 + 2 = 25 + 2 = 27 = 3^3\). Hence, by \(b^2 + a = 3^k\), the only solution of the equations is \((a, b, m, k) = (2, 5, 2, 3)\).

12. **Case 2:** \(b + a - 1 = 3^{m-1}t\). Then according to \(a^2 + b = 3^m\):
   \[
   (a^2 + b)t = 3^m \cdot t = 3(b + a - 1),
   \]
   i.e.,
   \[
   (3 - t)b = ta^2 - 3a + 3.
   \]
   If \(t = 1\), then \(a^2 - 3a + 3\) is even, which is impossible since \(a^2 - 3a\) is even. Consequently, \(t = 2\) by contradiction, which inserted in the equation gives us:
   \[
   b = 2a^2 - 3a + 3.
   \]
   Combining \(a^2 + b = 3^m\) and \(b = 2a^2 - 3a + 3\), we find that:
   \[
   3^m = a^2 + b = a^2 + (2a^2 - 3a + 3) = 3(a^2 - a + 1),
   \]
   i.e.,
   \[
   a^2 - a + 1 = 3^{m-1}.
   \]
   The fact that \(9 \nmid a^2 - a + 1\) combined with \(a^2 - a + 1 = 3^{m-1}\) yields \(m \leq 2\). Thus, \((a, b) = (1, 2)\) or \((a, b) = (2, 5)\) by the equations. From Case 1, we know that the only solution is \((a, b) = (2, 5)\) with \((k, m) = (3, 2)\).

Conclusion:
The only pair of distinct natural numbers \((a, b)\) satisfying the conditions is \((a, b) = (2, 5)\).

The final answer is \( \boxed{ (a, b) = (2, 5) } \).