$m+n$

- if $\gcd(m,n) > 1$ or $m,n$ are both odd then no such $k$ exists. - if $\gcd(m,n) = 1$ and one of them, say $m$ is even, then the answer is $$\max\{2p,m\} + \max \{q,n\}$$where $p$ is defined as the least $t\geq 0$ such that $2mt\equiv \pm 1\pmod{n}$ and $q$ is defined as either $\frac{2mp-1}{n}$ or $\frac{2mp+1}{n}$, whichever is the lower-valued integer.

Clearly, if $\gcd(m,n)>1$ there is no such $k$. Also, if $m,n$ are both odd, chessboard coloring show there is no such $k$. Now WLOG assume $m$ is even and $n$ is odd. Classify the moves into two types - type 1 : $(x,y)\to(x\pm m,y\pm n)$ and type 2 : $(x,y) \to (x\pm n,y\pm n)$. Since the order of moves doesn't matter, assume all type 1 moves are done first then the type 2 moves. Now note that we can use only type 1 moves to go from $(x,y)\to(x\pm am,x\pm bn)$ iff $a\equiv b\pmod{2}$, and when this occurs, we'll need $\max\{|a|,|b|\}$ type 1 moves. The same holds true for type 2 moves too. We want something like this: $$(0,0) \xrightarrow[\text{type 1 only}]\ (am,bn) \xrightarrow[\text{type 2 only}]\ (am+cn,bn+dm) = (1,0)$$Since $(m,n)=1$, $m\mid b$ and $n\mid d$, so $b$ must be even. Thus $a$ is even too. Write $a=2s$. Now we want $2sm+cn=1$. Any solution $(s,c)$ of this will lead to a series of $\max\{2|s|,|b|\}+\max\{|c|,|d|\}\geq\max\{2|s|,m\}+\max\{|c|,n\}$ moves. We aim to minimize this, which is basically minimizing $|s|$, and this leads to our answer.