These are just several thoughts. but it seems that they show in particular that the answr is $0$ for $k< p^p-1$.
$\def\FF{{\mathbb F}}$ 1. Firstly, denoting $d=\mathop{\rm lcm}(p-1,p^2-1,\dots,p^p-1)$ we see that $A^{pd+p}=A^p$ for every matrix $A$ (the order of a semisimple component divides $d$, and we need $p$ in order for a nilpotent component to vanish). Thus we may assume that $k < pd+p$.
2. Your sum is equal to $$ S=\sum_{a_{11}\in\FF_p} \dots\sum_{a_{pp}\in\FF_p} \left(\sum_{i=1}^p\sum_{j=1}^p a_{ij}E_{ij}\right)^k, $$ Now expand the inner brackets; we obtain $$ S=\sum_J \left(\sum_{a_{11}\in\FF_p} \dots\sum_{a_{pp}\in\FF_p} a^J\right)M_J, $$ where the outer summation is taken over some multiindices $J$ with $|J|=k$, and $M_J$ are some matrices. The summation in brackets over $a_{ij}$ gives zero unless the exponent of $a_{ij}$ is nonzero and divisible by $p-1$. Thus the sum in the brackets vanishes unless all the coordinates of $J$ are nonzero and divisible by $p-1$. So, if $k < p^2(p-1)$ then $S=0$, as is in the case $k=80$ and $p=17$.
3. For the remaining case, we need to calculate $M_J$. Assume that $J=(j_{11},\dots,j_{pp})$ (all $j$'s are multiples of $p-1$). Consider a digraph $G_J$ with $\FF_p$ as the set of vertices and $j_{k\ell}$ edges from $k$ to $\ell$. Now, if $M_J=[m_{k\ell}]$ then $m_{kk}$ is the number of Eulerian paths starting at $k$ (multiplies by the sum in brackets which is $-1$), and all other entries are zeroes.
Now let us show that the number of such cycles is divisible by $p$. We will assume that $k=1$, so that the cycles start and end at $1$. Split each cycle into subcycles starting at $1$, ending at $1$ and not passing through $1$ any more. Correspond to each cycle all the cycles obtained by permutatons of subcycles; thus the set of all cycles is partitioned into such equivalence classes, and the number of elements in each class is a corresponding multinomial coefficient $\binom{k}{s_1,\dots,s_t}$ where $s_1,\dots,s_t$ are the numbers of occurences of different subcycles. This coefficient is divisible by $p$ unless in the $p$-adic notation there are no transitions in the addition $s_1+\dots+s_t=k$.
Notice that there are at least $p$ distinct subcycles --- at least one starting from each of the edges $1\to 1$, $1\to 2$, \dots, $1\to p$. Moreover, we may partition all the subcycles into such classes --- the number in each will be divisible by $p-1$. THus, we have $p$ nonzero numbers divisble by $p-1$, and there shpuld be no transitions in addition of these $p$ numbers; this may happen only if $k\geq (p-1)+p(p-1)+\dots+p^{p-1}(p-1)=p^p-1$. So, for $k< p^p-1$ we definitely have $S=0$.
EDIT. Below in the comments, several improvements of this bound are shown.