Family of GCDs all equal to $2$

No, it's not true. $p=3\cdot 2^{2208}+1$ divides the GCD when $n=2206$.

If $p=3\cdot 2^{n+d}+1$ with $d>0$ then $x^{2^n}+1\equiv 0\pmod{p}$ has $2^n$ distinct roots in $[1,p-1]$. For $d=1$ this means $1/6$ of all residues are roots, and if you imagine their appearance in this class "looks random" in some sense, then for about $1/36$ of such primes both $5$ and $13$ will be roots.

Similarly when $d>1$ and also for primes of the form $k\cdot 2^{n+d}+1$ we can optimistically expect a fixed fraction of primes in the pattern to give counterexamples.

There's no guarantee because there may be some hidden structure, but I thought it likely that I could find a small-ish counterexample. Unfortunately I couldn't find one with $d=1$.