As you have noticed, $p \equiv 1 \bmod 4$. Then $1 \equiv n^{p-1} = (n^4)^{(p-1)/4} \equiv (-1)^{(p-1)/4} \bmod p$. This means that $(p-1)/4$ is even, i.e., $p\equiv 1 \bmod 8$.
By induction, this argument generalizes to: if an odd prime $p$ divides a number of the form $n^k+1$, where $k$ is a power of $2$, then $p \equiv 1 \bmod {2k}$.
I have not thought about this particular problem yet, but let me prove somewhat related claim that if $x,y$ are integers and $x^n-1$ divides $y^n-1,$ $y>1$ for all $n\in\mathbb{N}$ (this condition can be eventually relaxed) then $y=x^m$ for some $m\in\mathbb{N}.$ This, in particular implies that both $x$ and $y$ cannot be primes simultaneously.
The key is the following useful lemma.
Lemma. If $x_1....x_m\ge 1$ are distinct rational numbers and $\alpha_1,...\alpha_m\ne 0$ are real numbers such that $\lim_{n\to\infty}\sum_{k=1}^m\alpha_kx_k^n-m_n=0$ where $m_n\in\mathbb{N},$ then $x_i\in\mathbb{Z},$ for $1\le i\le m.$
Proof. Induction on $m.$ The base case is fairly interesting exercise, I will leave it for the reader. To prove a step of induction from $m$ to $m+1,$ we fix some $x_l=\frac{p}{q}.$ Observe, that
$$\lim_{n\to\infty}\sum_{k=1}^mp\alpha_kx_k^n-pm_n=0$$
and
$$\lim_{n\to\infty}\sum_{k=1}^mq\alpha_kx_k^{n+1}-qm_{n+1}=0.$$
Subtracting last two identities leads to
$$\lim_{n\to\infty}\sum_{k=1}^m\alpha_kx_k^n(qx_k-p)-(qm_{n+1}-pm_n)=0.$$
Since $x_lq-p=0,$ we can apply induction hypothesis to conclude that $x_i\in\mathbb{N}$ for $i\ne l.$ We are left to note that $l$ was chosen arbitrary and thus, $x_i\in\mathbb{N}$ for $1\le m+1.$
Now, in order to apply this to our problem we pick such $m$ that $x^m\le y<x^{m+1}$ and take $m_i=\frac{y^i-1}{x^i-1},$ $x_i=\frac{y}{x^i},$ $\alpha_i=1$ for $1\le i\le m.$ Then
$$m_n-\sum_{k=1}^m\alpha_kx_k^n=\frac{y^n-x^{mn}}{x^{mn}(x^n-1)}\to 0.$$
So all $x_i$ are integers. Thus, $$\frac{y^n-x^{mn}}{x^{mn}(x^n-1)}=0$$
for sufficiently large $n.$ Therefore $y=x^m.$
Note, that we can request $\lim_{n\to\infty}\sum_{k=1}^m\alpha_kx_k^n-m_n=0$ along some "fairly nice" subsequence $n_k.$ Thus, we do not require divisibility $x^n-1$ and $y^n-1$ for all $n.$
Remark 1. As to the second question, I do not think that there is something special about $n,$ in the sense that it can be fairly large. Good computer search should help to find a counterexample.
Remark 2. Starting from any prime $q$ and any $a>1,$ and $q^n-1$ divides $a^n-1$ we can take $x_m=a+m(q^{n}-1)$ and apply Dirichlet's theorem for arithmetic progressions to find infinitely many primes that satisfy our condition.
Best Answer
The solution has been posted on this post on AoPS
To continue the solution outlined in the comment(which is similar to the AoPS solution, but we are constructing an $a$ such that $(a - i + 1)^2 + (a + i)^2(1 \leq i \leq 2019)$ are consecutive elements of $a_n$), you can
Take $a$ to be divisible by $10000!$, so that $(a - i + 1, a + i) = 1$ for all $1 \leq i \leq 2019$.
For each $j \in [1, 2018^2 + 2019^2]$ such that $2j + 1$ is not a square, pick a distinct prime $p_j \equiv 3 \bmod 4$ greater than $10000$ and a $b_j$ such that $p | (2b_j + 1)^2 + 2j + 1$. It is possible to show that infinitely many such $p_j$ exists as $2j + 1$ is not a square. By CRT, we can take $a$ such that $a \equiv b_j \bmod p_j$ for each $j$. This ensures that $2a^2 + 2a + j$ cannot be written as $x^2 + y^2$ for $x,y$ coprime.