Suppose $m,n,k$ are positive integers with $m-1|kn-1$ and $n-1|km-1$. Is it true that the largest solution $(m,n)$ with $m\ge n$ has $m=k^3$? If not, is there an upper bound in terms of $k$ for what $\max\{m,n\}$ can be?
This question follows from numerical conjecture - indeed, if we have $k=3$ the largest possible value for $m$ is $27$; $64$ in the case $k=4$ and $125$ in the case $k=5$. I don't know how to prove it though. An attempt would be to say that the first divisibiltiy requires $kn-1=a(m-1)$ for some $a\in\mathbb{N}$, so $n=\frac{1+am-a}{k}$, and then the second divisibility gives that there is a positive integer $b$ such that $km-1=bn-b$. Substitute in the above result to see that $km-1+b=\frac{b+bam-ba}{k}$. Hence \begin{equation}k^2m-k+kb=b+bam-ba\end{equation}which then reduces to \begin{equation}m(k^2-ba)-k+kb-b+ba=0\end{equation} so $m(k^2-ba)+k(b-1)+b(a-1)=0$. I can't see how to bound $m$ from this though. Alternatively, we could maybe write this in terms of $k$ but I don't see how this would help.
You've made a great start. Your conjecture is correct, i.e., for each $k \ge 2$, with $m \ge n$, the largest value of $m$ is $m = k^3$.
With your last equation, and using some of the reasoning in your linked case $k = 4$ answer, we get
$$\begin{equation}\begin{aligned} m(k^2 - ba) + k(b - 1) + b(a - 1) & = 0 \\ m(ba - k^2) & = k(b - 1) + b(a - 1) \\ m(ab - k^2) & = ab + (k - 1)b - k \end{aligned}\end{equation}\tag{1}\label{eq1A}$$
Using $a = b = 1$ gives $m(1 - k^2) = 0$. However, this requires $m = 0$, but it's not allowed since $a$, $b$ and $m$ are positive integers. For all other positive values of $a$ and $b$, the RHS of \eqref{eq1A} is positive, so then $ba - k^2 \gt 0$, i.e., there's an integer $c \gt 0$ where
$$ab - k^2 = c \;\to\; ab = c + k^2 \tag{2}\label{eq2A}$$
Dividing both sides of \eqref{eq1A} by $c$, and using \eqref{eq2A}, we have
$$m = \frac{c + k^2 + (k - 1)b - k}{c} \tag{3}\label{eq3A}$$
For any fixed $c$, and since $k$ is fixed, the value of $m$ above is maximized with the largest possible value of $b$. The RHS of \eqref{eq2A} shows this occurs when $a = 1$, to get $b = c + k^2$. Substituting this into \eqref{eq3A} gives
$$\begin{equation}\begin{aligned} m & \le \frac{c + k^2 + (k - 1)(c + k^2) - k}{c} \\ & = \frac{c + k^2 + ck + k^3 - c - k^2 - k}{c} \\ & = \frac{ck + k^3 - k}{c} \\ & = k + \frac{k^3 - k}{c} \end{aligned}\end{equation}\tag{4}\label{eq4A}$$
Since $k^3 - k \gt 0$, then $c$ increasing causes the RHS to decrease, so the maximum value of the RHS occurs where $c = 1$, to then get
$$m \le k + k^3 - k = k^3 \tag{5}\label{eq5A}$$
Your first divisibility result with $a = 1$ then gives
$$kn - 1 = a(m - 1) \;\;\to\;\; kn = k^3 \;\;\to\;\; n = k^2 \tag{6}\label{eq6A}$$
The original divisibility requirements are met since
$$m - 1 \mid kn - 1 \;\;\to\;\; k^3 - 1 \mid k^3 - 1, \;\;\; n - 1 \mid km - 1 \;\;\to\;\; k^2 - 1 \mid k^4 - 1 \tag{7}\label{eq7A}$$
with the latter part using that $k^4 - 1 = (k^2 - 1)(k^2 + 1)$. This confirms that the maximum $m = k^3$ gives a valid solution of $(m, n) = (k^3, k^2)$.