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$.