If $\alpha$ is separable over $k$, then we can take either $n=0$ (if $\alpha\in k$), or $m=0$ (if $\alpha\notin k$). So we may assume that $\alpha$ is not separable over $k$.
Recall that if $k$ is a field of characteristic $p\gt 0$, and $f(x)\in k[x]$ is irreducible, then $f$ is not separable if and only if it can be expressed as a polynomial in $x^p$; indeed, $f$ is not separable if and only if $f$ has repeated roots; if and only if $f$ is not relatively prime with its formal derivative f'; if and only if (since we are assuming $f$ is irreducible) f'=0; if and only if $f$ is a polynomial in $x^p$.
So let $f(x)$ be the minimal polynomial of $\alpha$ over $k$. Then $f(x) = g(x^p)$ for some polynomial $g(x)\in k[x]$, since $\alpha$ is not separable. Let $\ell$ be the largest integer such that $f(x) = h(x^{p^{\ell}})$ for some $h(x)\in k[x]$. In particular, $h(x)$ is separable, since it must be irreducible (as $f$ is irreducible), and cannot be a polynomial in $x^p$ by the definition of $\ell$. If $h(x)$ is of degree one, then $\alpha^{p^{\ell}}\in k$, so take $n=\ell$. If $h$ is not linear, then let $m=\ell$; then $\beta=\alpha^{p^m}$ is a root of $h(x)$, does not lie in $k$, and is separable over $k$.