Eigenvalues versus algebraic closedness
While you can explicitly construct a matrix with given characteristic polynomial, I rather like the following more abstract argument. Suppose $k$ is not algebraically closed. Then it has a nontrivial finite field extension $K$ (you can adjoin a root of any nonlinear irreducible polynomial). Picking a basis for $K$ as a $k$-vector space, for any $a\in K$ we can represent multiplication by $a$ as a matrix $T_a$. If $a\in K\setminus k$, then $T_a-\lambda I=T_{a-\lambda}$ is invertible for any $\lambda\in k$: its inverse is just $T_{(a-\lambda)^{-1}}$. Thus $T_a$ is a matrix with no eigenvalues over $k$.