Suppose $J$ is the $n\times n$ Jordan Block matrix with all zero eigenvalues, (a.k.a. the "shift" matrix)
$\begin{pmatrix} 0&1&...&0&0\\0&0&...&0&0\\\vdots&\vdots&\ddots&\vdots &\vdots\\0&0&...&0&1\\0&0&...&0&0\end{pmatrix}$,
Is it the case that the $C^*(J,I)=\overline{\{\sum c_{kj}J^kJ^{*j}:c_{k,j}\in\mathbb{C}, \text{finite sums}\}}=M_n(\mathbb{C})?$ (i.e. Is the algebra generated by $\{I, J, J^*\}$ all of $M_n$?)
I can generate the basis $\{E_{ij}\}$ of $M_3$ pretty easily, and I've been able to find enough for $M_4$ that it seems promising, but I don't see a nice algorithm yet.
Here's one method: note that $$ E_{n,1} = J^{n-1} $$ From there, note that $$ P = J^{n-1} + J^* $$ is a permutation matrix, which allow you to permute the rows/columns of any matrix. Using these two, we can generate all matrices $E_{ij}$. Thus, we indeed have that the algebra generated is all of $M_n(\Bbb C)$.