$AB-BA=A^k$, then $A$ is not invertible

Use the same idea: $A^{-k}(AB-BA)=I_n$ implies that $A^{1-k}B-A^{-k}BA=I_n$, we deduce that:

$A^{1-k}B=I_n+A^{-k}BA$ and $tr(A^{1-k}B)=Tr(I_n)+Tr(A^{-k}BA)$, since $Tr(A^{1-k}B)=Tr(A^{-k}BA)$ you have the contradiction.

Multiplying on left by $A$ we get

$$A^{k+1}=A^2B-ABA=A^2B-BA^2-A^{k+1}$$ which gives

$$A^2B-BA^2=2A^{k+1}$$ and then we see by induction that

$$A^{p+1}B-BA^{p+1}=(p+1)A^{p+k}$$ Now assume that $A$ invertible and define the linear map $\varphi: M\mapsto MA^{-k+1}B-BA^{-k+1}M$ then $$\varphi(A^{p+k})=(p+1)A^{p+k}, \forall p$$ which means that $\varphi$ has an infinite set of eigenvalues in finite dimensional space which is a contradiction.

If you multiply by any power of $A$ (left or right) and take the trace, you get that for all $p \ge k$, $Tr(A^p)=0$. In $\mathcal{M}_n\big(\mathbb{C}\big)$, you can triangularize $A$. With $a_1,...,a_n$ the diagonal entries, the equality above about the trace can be rewritten: for all $p \ge k$, $a_1^p+\cdot\cdot\cdot+a_n^p=0$, from which you can easily prove that $a_1=...=a_n=0$ (only keep the non-null $a_i$ and rewrite the inequality using a Vandermonde-like matrix).

Hence $A$ is nilpotent.