Wow, I didn't know that you propose inequalities as well! I claim that the answer is $10$. We can check cases for $n=1,2$ and see that $k=10$ is the largest value that always works here (in particular equality only for $(3,2)$). Hence the answer is at most $10$. Now we may assume $\min (m,n) \geq 3$ Now $m^3 + n^3 \geq 3(m^2+n^2) \geq (m+n)^2 + m^2 + n^2 \geq (m+n)^2 + 18 > (m+n)^2 + 10$. So $10$ works everywhere. Edit: $1400$th post yay

честно гововря у тебя не в темская решения

My inexperience shows in my solution, but I will share it anyways for fun. I would appreciate if anyone has any comments on how I can improve my proof-writing, whenever I prove, I write really long proofs. First, we find the condition for which the given inequality is satisfied. WLOG assume $m \geq n$, so let $m = n+c$, where $c$ is a nonnegative integer. Plugging $m = n+c$ in, we get $$(n+c)^3 - (n+c)(n) + n^2 > (n+c) + n$$$$n^2 +(c-2)n+(c^2-c) > 0.$$Now, notice that if the discriminant is less than $0$ (no solutions) then the inequality is always true. Let's solve $$(c-2)^2 -4(c^2-c) < 0$$$$c^2 > \frac{4}{3} \implies c \geq 2.$$Therefore, when $c \geq 2$, all $n$ work. Next, suppose $c = 1$, then $$n^2 -n > 0$$$$n \geq 2.$$And when $c = 0$: $$n^2-2n > 0$$$$n \geq 3.$$Now for the main part of the proof. I claim that the maximum $k$ is $10$. The pair $(2, 3)$ satisfies the given inequality, and so $35 \geq 25+k$, meaning $k \leq 10$. Now, to prove $k = 10$ works, we take cases on $c \geq 2$, $c = 1$, and $c = 0$. If $c \geq 2$, it suffices to prove $$(n+c)^3 +n^2 \geq (n+c)^2 +2n(n+c)+n^2+10$$$$\iff n^3 +n^2+2n \geq 3.$$The left hand side is increasing for all positive $n$, and $n = 1$ satisfies the inequality, so the inequality is true for all $n \geq 1$, so this case is settled. Now suppose $c = 1$, then we know $n \geq 2$ and it suffices to prove $$(n+1)^3 +n^2 \geq (2n+1)^2 +10$$$$n(n-1)(2n+1) \geq 10.$$The left hand side is increasing for all $n > 1$, and $n = 2$ is true, therefore this case is satisfied as well. Finally, when $c = 0$, we have $n \geq 3$, and it suffices to prove $$2n^2 \geq 4n^2+10$$$$n^2(n-2) \geq 5.$$The left hand side is increasing when $n>2$, and $n = 3$ works, so this case is satisfied as well. Therefore, $k = 10$ works and is the maximum.

We claim that the answer is $\fbox{10}$. Take $(m,n)=(3,2)$. Then, we have $m^3+n^3-(m+n)^2=10$, so $10$ works and $k\le 10$,. Now it suffices to prove that any $10$ works for any $(m,n)$ satisfying the given condition. Note that the condition is equivalent to $S=(m-n)^2+(m-1)^2+(n-1)^2>2\dots (*)$. Additionally, by checking the parities of $m,n$, note that $S$ is even. WLOG $m\ge n$. Firstly, we will prove that $m+n\ge 4$. Suppose otherwise. Then, $m+n=2$, which gives us $(m,n)=(1,1)$, or $m+n=3$, which gives us $(m,n)=(2,1)$. We can check that both pairs do not satisfy $(*)$. Next, we can check the case when $m+n=4$, i.e. when $(m,n)=(3,1)$ or $(m,n)=(2,2)$. The first pair gives us $m^3+n^3-(m+n)^2=12>10$ while the second pair doesn't satisfy $(*)$. Now, we check the case when $m+n\ge 5$. When $m+n\ge 5$, $m\ge 3$, so $S\ge 4$. However, $4$ is not attainable as that will cause $m=3$ and $m-n=n-1=0$, which is a contradiction. Therefore, $S\ge 6$ since $S$ is even. Thus, for $m+n\ge 5$, we have \[m^3+n^3-(m+n)^2=(m+n)(m^2-mn+n^2-m-n)=(m+n)\left(\frac{S-2}{2}\right)\ge 5\cdot \left(\frac{6-2}{2}\right)=10,\]which completes the proof of our claim. $\blacksquare$