Is $x^p-x+1$ always irreducible in $\mathbb F_p[x]$?
This is true. Pass to an extension field where the polynomial has a root $r$, notice that the other roots are of the form $r+1$, $r+2$, ..., $r+p-1$. Suppose that $x^p - x +1 = f(x) g(x)$, with $f, g \in \mathbb{F}_p\left[x\right]$ and $\deg f = d$. Then $f(x) = (x-r-c_1) (x-r-c_2) \cdots (x-r-c_d)$ for some subset $\{ c_1, c_2, \ldots, c_d \}$ of $\mathbb{F}_p$. So the coefficient of $x^{d-1}$ in $f$ is $-\sum (r+c_i) = - (dr + \sum c_i)$; we deduce that $dr \in \mathbb{F}_p$. If $d \neq 0 \bmod p$, then $r \in \mathbb{F}_p$ which is plainly false, so $d=0$ or $p$ and the factorization is trivial.
If I were to try to turn this proof into a general technique, I suppose I would frame it as "prove that the Galois group is contained in a cyclic group of order $p$, and observe that it can't be the trivial group, so it must be the whole group."
I can also prove the generalization. Define a $\mathbb{F}_p$-module endomorphism $T$ of any commutative $\mathbb{F}_p$-algebra by $T(u) = u^p-u$. Set $F(n) = \mathbb{F}_{p^{p^n}}$. Observe that $$T^r(x) = \sum_{k=0}^r (-1)^{r-k} x^{p^k} \binom{r}{k}.$$
Lemma $T$ is an $\mathbb{F}_p$-linear endomorphism of $F(n)$ whose Jordan-normal form is a single nilpotent block (of size $p^n$).
Proof Obviously, $T$ is $\mathbb{F}_p$-linear. Observe that $$T^{p^n}(x) = \sum_{k=0}^{p^n} (-1)^{p^n-k} x^{p^k} \binom{p^n}{k} = x^{p^{p^n}} - x$$ so $T^{p^n}$ is zero on $F(n)$ and we know that $T$ is nilpotent. Finally, $T(x) = x^p-x$ so the kernel of $T$ is one dimensional, and we see that there is only one Jordan block. $\square$
Now, let $p^{n-1} \leq r < p^n$. Roland's polynomial is $T^r(x) = a$ for $a$ a nonzero element of $\mathbb{F}_p$. Using the Lemma, the image of $T^r: F(n) \to F(n)$ is the same as the kernel of $T^{p^n-r}$. In particular, since $a \in \mathrm{Ker}(T)$, we see that $a$ is in the image of $T^r: F(n) \to F(n)$. Using the Lemma again, all nonzero fibers of $T^r$ are of size $p^r$, so there are $p^r$ roots of $T^r(x)=a$ in $F(n)$. Since Roland's polynomial only has degree $p^r$, we see that all roots of $T^r(x)=a$ are in $F(n)$.
All proper subfields of $F(n)$ are contained in $F(n-1)$. But, since $r \geq p^{n-1}$, the Lemma shows that $T^r(x)=0$ on $F(n-1)$. So none of the roots of $T^r(x)=a$ are in $F(n-1)$.
We conclude that all the factors of Roland's polynomial are of degree $p^n$.
Here is an alternate proof of the OP's first conclusion, based on the same idea as David's, but which avoids consideration of coefficients. Let $r$ be a root of $h(x):=x^p-x+1$, so that $r\notin\mathbf{F}_p$. Since $h(x+c)=h(x)$ for every $c\in\mathbf{F}_p$, the other roots of $h(x)$ are $r+1,r+2,\dots,r+p-1$. Let $f(x)$ be the minimal polynomial of $r$ over $\mathbf{F}_p$, and let $r+c$ be a root of $f(x)$ with $c\ne 0$. Write $h(x)=f(x)g(x)$, so that $$ f(x+c)g(x+c)=h(x+c)=h(x)=f(x)g(x). $$ Since $f(x)$ and $f(x+c)$ are monic irreducible polynomials in $\mathbf{F}_p$ which both have $r$ as a root, they must be the same polynomial. Therefore the set of roots of $f(x)$ is preserved by the map $s\mapsto s+c$, so this set must include all the roots of $h(x)$.
I mention this variant of David's proof mostly in case this version might suggest generalizations to different types of settings.
Here is a proof of the OP's more general conclusion. Write $L(x)^{\circ n}$ for the $n$-th iterate of $L(x):=x^p-x$. We compute $$ L(x)^{\circ n} = (L(x)^{\circ (n-1)})^p-L(x)^{\circ (n-1)}=L(x)^{\circ (n-1)}\prod_{a=1}^{p-1} (L(x)^{\circ (n-1)}+a) $$ $$= L(x)^{\circ (n-1)}\prod_{a=1}^{p-1}\Bigl( a + \sum_{j=0}^n {n\choose j}(-1)^jx^{p^j}\Bigr). $$ It follows that $L(x)^{\circ n}$ is divisible by $L(x)^{\circ (n-1)}$, and the goal is to prove that for every $n$ there exists $k$ so that every irreducible factor of $f_n(x):=L(x)^{\circ n}/L(x)^{\circ (n-1)}$ in $\mathbf{F}_p[x]$ has degree $p^k$.
The key step in the proof is the following claim: if $u$ is a root of $f_n(x)$, then all roots of $f_n(x)$ have the form $iu+L(w)$ where $i\in\mathbf{F}_p$ and $L^{\circ n}(w)=0$. To prove this, first note that $L(x+dy)=L(x)+dL(y)$ for any $d\in\mathbf{F}_p$, so that $L^{\circ n}(iu+j)=0$ for every $i\in\mathbf{F}_p$ and every root $j$ of $L^{\circ (n-1)}(x)$. But the polynomial $L^{\circ (n-1)}(x)$ is squarefree (since its derivative is $1$), so its roots form an $(n-1)$-dimensional $\mathbf{F}_p$-vector space, and since $L^{\circ (n-1)}(u)\ne 0$ it follows that the above values $iu+j$ comprise $p^n$ distinct roots of $L^{\circ n}(x)$, so every root has this form. Since $L^{\circ (n-1)}(j)=0$, we can write $j=L(w)$ for some root $w$ of $L^{\circ n}(x)$, which proves the claim.
Now we prove by induction on $n$ that for every $n$ there exists $k$ so that every irreducible factor of $f_n(x)$ in $\mathbf{F}_p[x]$ has degree $p^k$. The base case $n=1$ is trivial (where $L(x)^{\circ 0}=x$ by definition). Inductively, suppose that all irreducible factors of $f_n(x)$ have degree $p^k$.
Let $r,s$ be roots of $f_{n+1}(x)$. Then $u:=L(r)$ and $v:=L(s)$ are roots of $f_n(x)$, so that $\mathbf{F}_p(u)=\mathbf{F}_{p^k}=\mathbf{F}_p(v)$, and by the above claim we have $v=iu+L(w)$ with $i\in\mathbf{F}_p$ and $L^{\circ n}(w)=0$. Note that $i\ne 0$ since $L^{\circ (n-1)}(v)\ne 0$. Also $w\in\mathbf{F}_{p^k}$, since if $w\ne 0$ then $w$ is a root of $f_{\ell}(x)$ for some $\ell\le n$, so that $w=L^{\circ (n-\ell)}(z)$ for some root $z$ of $f_n(x)$, where $z\in\mathbf{F}_{p^k}$ by inductive hypothesis.
By the Artin-Schreier theorem, $[\mathbf{F}_p(r):\mathbf{F}_{p^k}]$ is either $1$ or $p$, and is $1$ if and only if $L(x)-u$ has a root in $\mathbf{F}_{p^k}$. This is equivalent to saying that $iL(x-w/i)-iu$ has a root in $\mathbf{F}_{p^k}$, or in other words (with $y=ix$) that $L(y)-(iu+j)$ has such a root, which in turn says that $[\mathbf{F}_p(s):\mathbf{F}_{p^k}]=1$. Therefore $\mathbf{F}_{p}(r)=\mathbf{F}_{p}(s)$, and this field is either $\mathbf{F}_{p^k}$ or $\mathbf{F}_{p^{k+1}}$, as desired.
You might be interested in Artin-Schreier theory.