Algorithm to sort n numbers from 0 to $n^m$ in $\mathcal{O}(n)$? where m is a constant
The reason of your confusion is that the computational model under which the algorithm is run is not specified.

Assuming you are allowed to perform arithmetic in $\mathcal{O}(1)$ time$^*$, then the $\mathcal{O}(mn)$ bound is correct. The reason is that you don't need to explicitly make base conversions. Since radix sort only ever compares digits of numbers, it is sufficient to provide a way to compare arbitrary digits in $\mathcal{O}(1)$ time$^{**}$; it is not hard to convince yourself that given an integer $x$, the $i$-th digit from the right in the base $b$ representation of $x$ is exactly:

$\qquad x/b^{i-1} \ \% \ b$

where $\%$ is the modulo operator.

Under more stringent conditions on arithmetic (such as classical random access machines or constantly-bounded Word-RAMs), both taking the modulo and division by a constant are operations that take logarithmic time, changing the running time of radix sort accordingly.



$^*$ For example, with a Word-RAM model with $w \ge \log n$.

$^{**}$ Notice that this is consistent with practice. If you have any sense, you would set $b$ to be a power of two in an implementation.