The origin of this question is the conjecture on the period $T_p$ of $n\mapsto B_n\bmod p$ for a prime $p$. [As of now, the question stands alone - the connection with the conjecture has lost its meaning; see the linked question.]
Touchard's congruence $B_{n+p}\equiv B_n+B_{n+1}\pmod{p}$ implies that $T_p$ (exists and) is a divisor of $$N_p=(p^p-1)/(p-1)$$ (the conjecture says $T_p=N_p$ for all $p$), and that, to test whether $m$ is a period of $n\mapsto B_n\bmod p$, it suffices to check $B_{m+n}\equiv B_n\pmod{p}$ for $0\leqslant n<p$. Which brings the following.
Given a prime $p$, how quickly (in terms of $p$) can one compute $$(B_0,B_1,\ldots,B_{p-1})\bmod p\tag{1}\label{initial}$$ and, more generally, $$(B_n,B_{n+1},\ldots,B_{n+p-1})\bmod p\tag{2}\label{shifted}$$ for an integer $n<N_p$ (or at least for a divisor of $N_p$)?
Of course, the verification of $T_p=N_p$ this way requires complete factorization of $N_p$, which is out of this question. (Still, in hope of a counterexample, one can try partial factorizations.)
The article referenced within gives simple algorithms. For $\eqref{initial}$, it is basically the triangular scheme requiring $\mathcal{O}(p^2)$ additions in $\mathbb{Z}/p\mathbb{Z}$, and for $\eqref{shifted}$, it is based on $B_{n+p^m}\equiv mB_n+B_{n+1}\pmod{p}$, a consequence of Touchard's, giving an $\mathcal{O}(p^2\log n)$ algorithm (again, counting operations in $\mathbb{Z}/p\mathbb{Z}$).
But we can do better. My own attempts are in an answer below.
For $(1)$, we have the following identity in $\mathbb{F}_p[x]$, where $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$: $$\sum_{n=0}^{p-1}B_n x^n=x^{p-1}+\sum_{n=0}^{p-1}x^n\prod_{k=n+1}^{p-1}(1-kx).$$ It is obtained from the formal power series $\sum_{n=0}^{\infty}B_n x^n$${}=\sum_{n=0}^{\infty}\prod_{k=1}^{n}\frac{x}{1-kx}$ using the identity $\prod_{k=1}^{p-1}(1-kx)\equiv 1-x^{p-1}$. (My initial idea was to use $\sum_{n=0}^{\infty}B_n x^n/n!=\exp(e^x-1)$ with fast composition; the above is a better one.) Rewriting, $\sum_{n=0}^{p-1}B_n x^n=x^{p-1}+Q_{0,p}(x)$, where $$P_{u,v}(x)=\prod_{k=u}^{v-1}(1-kx),\qquad Q_{u,v}(x)=\sum_{n=u}^{v-1}x^n P_{n+1,v}(x),$$ and, for $u\leqslant v\leqslant w$, we have $$P_{u,w}(x)=P_{u,v}(x)P_{v,w}(x),\qquad Q_{u,w}(x)=Q_{u,v}(x)P_{v,w}(x)+Q_{v,w}(x),$$ which gives a divide-and-conquer approach. Assuming multiplication of degree-$d$ polynomials done in $\mathcal{O}(d\log d)$ operations, this results in an $\mathcal{O}\big(p(\log p)^2\big)$ algorithm.
For $(2)$, let's reformulate Touchard's congruence in operator terms. Consider the vector space (over $\mathbb{F}_p$) of all sequences in $\mathbb{F}_p$, its subspace $\mathscr{B}_p$ generated by $e_k : n\mapsto B_{n+k}\bmod p$, and the "step operator" $S$ on $\mathscr{B}_p$ that sends $e_k$ to $e_{k+1}$ for each $k$. Then the congruence says $S^p=S+I$, where $I$ is the identity operator. So, the arithmetics of polynomials in $S$ is the one of $\mathbb{F}_p[x]$ modulo $x^p-x-1$; in particular, $S^{p^m}=S+mI$ (already stated in the OP) and, more generally, $$n=\sum_{k=0}^{d}n_k p^k\implies S^n=\prod_{k=0}^{d}(S+kI)^{n_k}.$$ Again, this can be computed by divide-and-conquer, this time in $\mathcal{O}\big(p(\log p)^3\big)$ operations.