This is the solution provided for the problem. However when I follow it, I am not getting the correct path. I assumed $N=4$ and $M=3$ and started with $k=0$ and got this path:
$$(0, 1) \to (0, 2) \to (1, 2) \to (1, 1) \to (2, 1) \to (2, 2) \to (3, 2)\to (3, 1) \to (4, 1) \to (0, 3)$$ $$\to (0, 2) \to (0, 1)$$ I got $(4,1)$ for $k=8$, which is wrong. But I can't figure out my mistake.
$N=4$, $M=3$, $k=8$, so $q=\lfloor \frac k{M-1}\rfloor = 4$, $r= k\bmod (M-1) = 0$. We are in the first bullet point, so visit $(q,r+1)=(4,1)$. Your computation is correct. The formulas do produce the sequence $$(0,1)\to (0,2)\to (1,2)\to (1,1)\to (2,1)\to (2,2)\to (3,2)\to \\ \to( 3,1)\to (4,1)\to (0,3)\to (0,2)\to (0,1)\to (0,0) $$ which is but not Hamiltonian for several reasons. (So much for "checking ... is routine")