The operation can be viewed as a graph connecting $a^k+b^k$ with $a^{k'}+b^{k'}$. Every number must be even. We claim that every even positive integer $\geq4$ works.
By the identity $(2x+y)^2+(x-2y)^2=5(x^2+y^2)=(2x-y)^2+(x+2y)^2$, we get $3x-y\rightarrow5(x^2+y^2)\rightarrow3x+y$ when $x>2y$, so this connects $2p$ and $2q$ for whenever $p<q$, $7p>5q$ and $3\mid p+q$ by taking $x=\frac{p+q}3$ $y=q-p$. In particular, $6k+2$ and $6k+4$ are connected for $k\geq1$ and $6k-2$ and $6k+2$ are connected for $k\geq3$. If $m$ is a multiple of $6$, then $m$ is connected to $1^2+(m-1)^2\equiv2\pmod6$, so every even integer greater than $14$ is connected to $14$. Now, the connections $m\rightarrow1+(m-1)^2$ gets the smaller integers.