This is false.

Let $p$ be an odd prime, let $\ell$ be another prime, and let $m$ be a small prime divisor of $p^{\ell}-1$, that doesn't divide $p-1$. Let $n= 1 + \frac{ p^{\ell}-1}{m}$.

Then $n-1$ is a multiple of $p-1$, is not a multiple of $p^{\ell}-1$, and is not a multiple of $p^{k}-1$ for any other $k$ because $p^{\ell}-1$ is not a multiple of $p^{k}-1$ for any $1 < k < \ell$.

Then $x \in \mathbb F_{p^\ell}$ is a root of $T^{n } - T$ if and only if $x$ is an $m$'th power in $\mathbb F_{p^\ell}$. So roots of the gcd of $(T+u)^n - (T+u)$ for all $u$ in $\mathbb F_p$ are exactly those $x \in \mathbb F_{p^\ell}$ such that $x = y_0^m, x+1 = y_1^m, \dots, x+p-1 = y_1^{m}$ for some $y_0, \dots, y_{p-1}$ in $\mathbb F_{p^\ell}$.

Thus, to find a counterexample, it suffices to check that the number of $\mathbb F_{p^\ell}$ points of the curve $C_m$ with variables $x,y_0,\dots, y_{p-1}$ and equations $x +i = y_i^m$ is greater than the number $p m^{p-1}$ of solutions with $x \in \mathbb F_p$. Then the $x$ coordinates of the extra points will be roots of the gcd but not roots of $T^p- T$.

By Riemann-Hurwitz, the genus $g$ of $C$ satisfies $$2-2g = 2 m^p - (p+1) m^{p-1} (m-1)$$ since the degree over $\mathbb P^1$ (under the map $x$) is $m^p$, there are $p+1$ branch points $0,1\dots, \infty$, and each branch point has ramification of order $m$ on each point lying above it. There are $m^{p-1}$ missing points at $\infty$.

So by Weil's theorem, the number of $\mathbb F_{p^\ell}$-points of $C$ is at least $$p^\ell - p^{\ell/2} ((p+1) m^{p-1} (m-1) + 2 - 2 m^p) +1 - m^{p-1}$$
with the first term the main term, the second term coming from the Frobenius eigenvalues, and the last term coming from the missing points.

Thus, as long as

$$ p^\ell > p^{\ell/2} ((p+1) m^{p-1} (m-1) + 2 - 2 m^p) + m^{p-1} + p m^{p-1},$$ there is a counterexample.

Plugging into Wolfram Alpha, this inequality fails for $p=3, \ell=11, m=23$ but succeeds for $p=3,\ell=23, m=47$ and $p=3, \ell=29, m=59$.

I found these by looking at the sequence of multiplicative orders of $3$ modulo primes and looking for prime values, which became $\ell$, with the modulus prime becoming $m$.

It seems there are many examples with $\ell$ not much smaller than $m$, which as long as both are much larger than $p$, means this inequality is easily satisfied, since anything of the form $p^\ell$ beats anything of the form $m^p$.

In the comments, François Brunault found an explicit example: The polynomial $$T^{23}-T^{22}-T^{21}-T^{20}-T^{19}+T^{18}-T^{16}+T^{13}+T^{12}+T^{11}-T^{10}+T^8+T^6+T^4-T^2-T-1$$ divides $$\gcd( T^{n} - T, (T-1)^n - (T-1) , (T+1)^n - (T+1))$$ in $\mathbb F_3[T]$ when $n= 1 + \frac{3^{23}-1}{47}$ and provided the following Pari/GP code to check it:

`P = Mod(x^23-x^22-x^21-x^20-x^19+x^18-x^16+x^13+x^12+x^11-x^10+x^8+x^6+x^4-x^2-x-1, 3); n = 1 + (3^23-1)/47; t = Mod(x, P); print(t^n == t & (t+1)^n == t+1 & (t-1)^n == t-1);`