Is it true that for every integer $k\neq 1$ there exists infinitely many natural numbers $n$ for which $2^{2^n}+k$ is a composite number?

Yes it is true, here is a proof. Suppose that $2^s$ is the highest power of $2$ dividing $k1$. Suppose also that all but finitely many numbers $2^{2^n}+k$ are primes. Take a very large such prime $p=2^{2^l}+k$, $l>s$. Then the maximal power of $2$ dividing $p1$ is $2^s$ and $m=\frac{p1}{2^s}$ is odd. Let $f=\phi(m)$ (the Euler function). Then $2^{ft}\equiv 1 \mod m$ for every $t\ge 1$. Then $2^{ft+s}\equiv 2^s \mod p1$. Hence $2^{ft+l}=2^l \mod p1$. Hence $2^{2^{ft+l}}\equiv 2^{2^l} \mod p$ and $2^{2^{ft+l}}+k\equiv 0 \mod p$, so it is never prime for $t\ge 1$. Update 1. One can of course replace $2$ by any natural number $>1$ in the above proof. It is not clear what to do with numbers $m^{n^b}+k$ for fixed $m,n,k$ when $m\ne n$, but see a comment above. Update 2. Actually the case $m\ne n$ is not very difficult either. Take a very large prime $p$ of the form $m^{n^l}+k$. We would like to have infinitely many $b$ such that $n^b\equiv n^l \mod p1$. The only thing needed for this is that $GCD(n^l,p1)=GCD(n^c,p1)$ for all big enough $c$. That seems to require very little work. 

