Find Jordan Decomposition of $\left(\begin{smallmatrix} 4 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 3 \end{smallmatrix}\right)$ over $\mathbb{F}_5$
Your calculations are fine. However, by definition of kernels, an element of the kernel of $(A+4E)^2$ vanishes when applying $A+4E$ to it twice, so you should not be surprised. You just made the wrong conclusion. The eigenvector $(3,0,1)$ together with the generalized eigenvector $(1,0,0)$ form part of a Jordan basis giving you a Jordan block of size $2$. All you need to do is add another eigenvector which is linear independent to $(3,0,1)$, for example $(1,1,2)$.
Then $$ \begin{pmatrix} 3 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 2 \end{pmatrix}^{-1} \begin{pmatrix} 4 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 3 \end{pmatrix} \begin{pmatrix} 3 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}. $$
Since $(A-I)(1,0,0)^T=(3,0,1)^T=3(1,0,2)^T$, a desired ordered basis is given by $\{(1,0,2)^T,\frac13(1,0,0)^T,(1,1,2)^T\}=\{(1,0,2)^T,(2,0,0)^T,(1,1,2)^T\}$.
You want three independent vectors, $v_1,v_2,v_3$ that have the properties:
$$Av_1=v_1, Av_2=v_2+v_1, Av_3=v_3.\tag{1}$$
For $v_2=(1,0,0)^T$ not in the eigenspace, we get $v_1=Av_2-v_2=(3,0,1)^T$ [*] and then you need a $v_3$ which is in the eigenspace of $A$ but not a multiple of $v_1.$ We'll choose $v_3=(0,1,0)^T.$ Then if $$S=\begin{pmatrix}v_1&v_2&v_3\end{pmatrix}=\begin{pmatrix}3&1&0\\0&0&1\\1&0&0\end{pmatrix}$$ then we can show:
$$J=\begin{pmatrix}1&1&0\\0&1&0\\0&0&1\end{pmatrix}=S^{-1}AS$$
Since $Se_i=v_i$ and the equalities in (1) and and $S^{-1}v_i=e_i,$ so we get $$Je_1=e_1,Je_2=e_1+e_2,Je_3=e_3$$
Since $\det S = 1$ even in the integers, we can use Wolfram Alpha to invert $S$ over the integers and get $$S^{-1}=\begin{pmatrix}0&0&1\\1&0&-3\\0&1&0 \end{pmatrix}$$
[*] Note that since $(A-E_3)^2=0,$ you have $A^2-A=A-E_3$ and hence, when $v_1=Av_2-v_2,$ you have $Av_1=(A^2-A)v_2=(A-E_3)v_2=Av_2-v_2=v_1.$
We could have started with any $v_2$ not in the eigenspace. We'll always get some multiple of our original $v_1$ for $v_1.$ Then $v_3$ can be any of $20$ vectors in the eigenspace not a multiple of $v_1.$