$\def\Z{\mathbb Z}
$This seems unlikely to be in the form you'd like, but, as you [requested](https://mathoverflow.net/questions/290029/jordan-decomposition-of-powers-of-the-shift-matrix#comment718905_290029), here is a slightly expanded version of my [comment](https://mathoverflow.net/questions/290029/jordan-decomposition-of-powers-of-the-shift-matrix#comment718903_290029).  There's no idea here, just computation, and you should check it yourself to make sure I haven't made (another) silly error.

For $k \in \Z$, put $\overline k = \{1, \dotsc, k\}$.  For $i \in \overline h$, let $e_i$ be the $i$th standard basis vector, so that $E_h^n e_i = e_{i + n}$ for all $i \in \overline{h - n}$ and $E_h^n e_i = 0$ for all $i \in \overline h \setminus \overline{h - n}$.  Let $\sigma \in \mathrm S_h$ be the permutation so that
$$
\sigma^{-1}(1, \dotsc, h) = (\underbrace{1, 1 + n, 1 + 2n, \dotsc}_{\lfloor(h - 1)/n\rfloor + 1}, \underbrace{2, 2 + n, 2 + 2n, \dotsc}_{\lfloor(h - 2)/n\rfloor + 1}, \dotsc, \underbrace{n, 2n, 3n, \dotsc}_{\lfloor(h - n)/n\rfloor + 1})
$$
(I made a fencepost error counting the size of each block in my [comment](https://mathoverflow.net/questions/290029/jordan-decomposition-of-powers-of-the-shift-matrix#comment718903_290029)), and $P$ the $h$-square permutation matrix with $P_{i j} = [\sigma(i) = j]$ for all $i, j \in \overline h$.  Then $P^{-1}E_h^n P e_j = e_{j + 1}$ for all $j \in \sigma(\overline{h - n})$, and $P^{-1}E_h^n P^{-1}e_j = 0$ for all $j \in \overline h \setminus \sigma(\overline{h - n})$.  That is, if, for $k \in \mathbb Q_{\ge 0}$, we write $J_k$ for the $(\lfloor k\rfloor + 1)$-square Jordan block
$$
J_k = \begin{pmatrix}
0      & 1      & 0      & \cdots & 0      \\
0      & 0      & \ddots & \ddots & \vdots \\
\vdots & \ddots & \ddots & 1      & 0      \\
0      & \cdots & 0      & 0      & 1      \\
0      & \cdots & 0      & 0      & 0
\end{pmatrix}
$$
(with $\lfloor k\rfloor$ $1$'s), then $C \mathrel{:=} P^{-1}E_h^n P$ equals $J_{(h - 1)/n} \oplus J_{(h - 2)/n} \oplus \dotsb \oplus J_{(h - n)/n}$.

Notice this gives the obvious right answer when $n = 1$, in which case $\sigma$ is the identity permutation.

For your example with $h = 5$ and $n = 2$, we have that
$$
\sigma^{-1}(1, 2, 3, 4, 5) = (\underbrace{1, 3, 5}_{\lfloor(h - 1)/n\rfloor + 1 = 3}, \underbrace{2, 4}_{\lfloor(h - 2)/n\rfloor + 1 = 2});
$$
that is, in cycle notation, $\sigma^{-1} = (2\ 3\ 5\ 4)$.