I think there are also infinitely many primes $p=4k+1$ such that $p\nmid n^{2016}+2016^{2016}$ for all $n$.
Suppose $p\mid n^{2016}+2016^{2016}$. As $2016= 2^5\cdot 3^2\cdot 7$, we have $(p,2016)=1$ so $p\mid u^{2016}+1$ where $u\equiv n\cdot 2016^{-1}\pmod{p}$. Further, let $d$ be the smallest positive integer for which $u^d\equiv 1\pmod{p}$. Then, $d\nmid 2016$ and $d\mid 2\cdot 2016$. This forces $v_2(d)=v_2(2016)+1=6$. We also have $d\mid p-1$ by Fermat, so $p\equiv 1\pmod{64}$ is a necessity. Now, just choose $p$ such that $p\equiv 1\pmod{4}$ and $p\not\equiv 1\pmod{64}$. For example, $p\equiv 5\pmod{64}$ is a valid choice and there're infinitely many such primes due to Dirichlet.