Hartley (http://primes.utm.edu/curios/page.php/71.html) gives that 13 and 71 divide $A(m,n)$ for sufficiently large $m$.

Since $\{A(m+1,n): n \geq N\} \subset \{A(m,n): n\geq A(m+1,N-1)\}$, we need only consider smaller $m$.

The case $m=4$ definitely involves $2\uparrow\uparrow k \bmod p$. If, for all primes $p$, $2 \uparrow\uparrow a \equiv 2 \uparrow\uparrow b \bmod p$, for sufficiently large $a,b$, then the $A(m,n)+c$, for fixed $c$, will be composite for sufficiently large $m$, since some prime $p$ will divide $A(4,n)+c$ for some large $n$ and then it will also divide $A(4,r)+c$ for $r \geq n$ if $n$ is sufficiently large, if the condition is true.

But $2 \uparrow\uparrow a \equiv 2 \uparrow\uparrow b \bmod p$ if $2 \uparrow\uparrow (a-1) \equiv 2 \uparrow\uparrow (b-1) \bmod (p-1)$ which is true if $2 \uparrow\uparrow (a-1) \equiv 2 \uparrow\uparrow (b-1)$ mod each prime power, say $q$, dividing $p-1$. But then this reduces to considering $2 \uparrow\uparrow (a-2) \equiv 2 \uparrow\uparrow (b-2) \bmod \varphi(q)$. The point is that the modulus keeps shrinking and eventually we can check $2\uparrow\uparrow k$ modulo small primes.

For example, $2\uparrow\uparrow k \equiv 1 \bmod 3$ and $2\uparrow\uparrow k \equiv 1 \bmod 5$ for sufficiently large $k$.

It seems then that for sufficiently large $m$, and fixed $c$, $A(m,n)+c$ cannot be prime. Does this work?