Let us consider the asymptotic density $d(A)$ of numbers (which form the set $A$) which can be covered by $x^a+y^b$. If we set $x^a+y^b\leq N$ we must have $0\leq N^{\frac{1}{a}}$ and $0\leq y\leq N^{\frac 1b}$. Therefore at most $O(N^{\frac 1a+\frac 1b})$ can be achieved less than $N$. If $\frac{1}{a}+\frac 1b<1$ this implies that the density is $0$. So now we have $d(A+S)=d(\bigcup_{s\in S}A+s)\leq \sum_{s\in S}d(A+s)=\sum_{s\in S}d(A)=|S|0=0$ so we get a contradiction. Now assume $\frac 1a+\frac 1b\geq 1$. If $a,b>1$ we have $\frac 1a+\frac 1b\leq \frac 12+\frac 12=1$ with equality if $a=b=2$, so let us look at this case. Since $S$ is bounded it suffices to show that here are arbitrarily long sequences of consecutive numbers which aren't sums of two squares. To do this, take $m$ primes $p_1,...,p_m$ all congruent to $3\pmod{4}$ (they exist by Dirichlet theorem) and take an $N$ such that $N+i\equiv p_i\pmod{p_i^2}$ for all $i=1,..,m$ it is well known that they can't be sums of squares, since they have a prime $\equiv 3\pmod 4$ with odd $p$-adic valutation. Therefore $(a,b)$ isn't a solution. Finally there remains the case $a=1$ or $b=1$ which trivially works since for example $x^1+0^b+0$ covers all nonnegative integers. Thus the answer is $(a,1)$ and $(1,b)$ for any $a,b$.

The idea is similar to above. Let $|S| = C$ and let $T(n) = |\{x^a + y^b + s \leq n: x,y \geq 0 , s \in S\}|$. Now we will estimate $T(n)$ from above. Note that if $x^a + y^b + s \leq n$, then $x \in [0,n^{\frac{1}{a}}) , y \in [0,n^{\frac{1}{b}})$. So, $x$ can take at most $n^{\frac{1}{a}}$ different values , $y$ can take at most $n^{\frac{1}{b}}$ different values and $s$ can take at most $C$ different values. So $T(n) \leq Cn^{\frac{1}{a} + \frac{1}{b}}$. But note that if $\frac{1}{a} + \frac{1}{b} < 1$, then $\lim_{n \to \infty} n - Cn^{\frac{1}{a} + \frac{1}{b}} = \infty$, which is a contradiction. Thus, $\frac{1}{a} + \frac{1}{b} \geq 1$. If $a$ or $b$ is $1$, assume WLOG that $a = 1$. Then taking $y=0$ we can write every natural number with $S = \{1\}$. If $a , b \geq 2$, then $a = b = 2$. Now we can finish as above and we are done.

Sadly similar to above posts. Suppose $S$ has $c$ elements. Consider a number $N$ which is sufficiently large and let $M = N^{ab}$ There are exactly $N^a$ numbers that are $b$th powers below $M$ and $N^b$ numbers that are $a$th powers below $M$. So, the set of numbers that can be written as $x^a + y^b$ is at most $(N^a)(N^b) = N^{a+b}$ and the set of numbers that can be written as $x^a + y^b + s$ is at most $cN^{a+b}$. But if $ab > a+b$, then we can pick $N$ to be big enough so that $N^{ab} > cN^{a+b}$ and so all numbers below $M$ cannot be represented. So, $ab \le a+b \implies (a-1)(b-1) \le 1$. If one of $a,b$ is $1$, then it obviously works, so assume $a,b > 1$ so the only other possibility is $a=b=2$. So it suffices to show that there exist arbitrarily long chains of consecutive positive integers, none of which can be written as the sum of two squares. To do this, it suffices to find arbitrarily long chains which all have at least one $3 \pmod 4$ prime factor, which can be done with CRT. So, the only solution is $(a,b) = (x,1), (1,x)$