Sketch of a proof: $A_0$ has $m$ elements smaller than or equal to $2^m$. You can form $m^2$ pairs of them, so $A_1$ has (at most) $m^2$ elements with an absolute value smaller than or equal to $2^m$ (the larger elements don't play a role, which can be seen by looking at the binary expansion). That means $A_n$ has at most $m^{2^n}$ elements with an absolute value smaller than or equal to $2^m$.

Suppose an $N$ would exist as described in (a). Take $m = N^N$, then $A_N$ has $N^{N2^N}=2^{N \log_2 N 2^N}$ elements with an absolute value smaller than or equal to $2^{N^N}$, while there are $2^{N^N}+1$ even numbers, which is much more. But again, looking at the binary expansion, $A_N$ should contain all even numbers.

So such an $N$ does not exist.

Sketch of a proof for (a): $A_0$ has $m$ elements smaller than or equal to $2^m$. You can form $m^2$ pairs of them, so $A_1$ has (at most) $m^2$ elements with an absolute value smaller than or equal to $2^m$ (the larger elements don't play a role, which can be seen by looking at the binary expansion). That means $A_n$ has at most $m^{2^n}$ elements with an absolute value smaller than or equal to $2^m$.

Every positive even number $s$ can be written (uniquely) as the sum of powers of 2 (again, look at the binary expansion): $s = \sum_{i=1}^{t}{2^{s_i}}$ with $t$ and each $s_i$ positive integers. Now $-(2^m) \in A_1$ for every positive integer $m$, and we can write $s = 2^{s_t} - (-(2^s_{t-1})) - (-(2^s_{t-2})) ... - (-(2^s_1))$ so $s \in A_t$. A similar sum/difference works for negative even numbers. So if an $N$ would exist as described in (a), $A_N$ should contain all even numbers.

Now take $m = N^N$, then $A_N$ has $N^{N2^N}=2^{N \log_2 N 2^N}$ elements with an absolute value smaller than or equal to $2^{N^N}$, while there are $2^{N^N}+1$ even numbers, which is (much) more.

Conclusion: such an $N$ does not exist.

Sketch of a proof: $A_0$ has $m$ elements smaller than or equal to $2^m$. You can form $m^2$ pairs of them, so $A_1$ has (at most) $m^2$ elements with an absolute value smaller than or equal to $2^m$ (the larger elements don't play a role, which can be seen by looking at the binary expansion). That means $A_n$ has at most $m^{2^n}$ elements with an absolute value smaller than or equal to $2^m$.

Suppose an $N$ would exist as described in (a). Take $m = N^N$, then $A_N$ has $N^{N2^N}=2^{N \log_2 N 2^N}$ elements with an absolute value smaller than or equal to $2^{N^N}$, while there are $2^{N^N}+1$ even numbers, which is much more. But again, looking at the binary expansion, $A_N$ should contain all even numbers.

So such an $N$ does not exist, and I think a similar argument would work for $k \ge 3$.

Sketch of a proof: $A_0$ has $m$ elements smaller than or equal to $2^m$. You can form $m^2$ pairs of them, so $A_1$ has (at most) $m^2$ elements with an absolute value smaller than or equal to $2^m$ (the larger elements don't play a role, which can be seen by looking at the binary expansion). That means $A_n$ has at most $m^{2^n}$ elements with an absolute value smaller than or equal to $2^m$.

Suppose an $N$ would exist as described in (a). Take $m = N^N$, then $A_N$ has $N^{N2^N}=2^{N \log_2 N 2^N}$ elements with an absolute value smaller than or equal to $2^{N^N}$, while there are $2^{N^N}+1$ even numbers, which is much more. But again, looking at the binary expansion, $A_N$ should contain all even numbers.

So such an $N$ does not exist.