Solution:
We see that for $m=3$ and $n=2$ we have $m^{3}+n^{3}>(m+n)^{2}$, thus
$$3^{3}+2^{3} \geq (3+2)^{2}+k \Rightarrow k \leq 10$$
We will show that $k=10$ is the desired maximum. In other words, we have to prove that
$$m^{3}+n^{3} \geq (m+n)^{2}+10$$
The last inequality is equivalent to
$$(m+n)\left(m^{2}+n^{2}-m n-m-n\right) \geq 10$$
If $m+n=2$ or $m+n=3$, then $(m, n)=(1,1),(1,2),(2,1)$ and we can check that none of them satisfies the condition $m^{3}+n^{3}>(m+n)^{2}$.
If $m+n=4$, then $(m, n)=(1,3),(2,2),(3,1)$. The pair $(m, n)=(2,2)$ doesn't satisfy the condition. The pairs $(m, n)=(1,3),(3,1)$ satisfy the condition and we can readily check that $m^{3}+n^{3} \geq (m+n)^{2}+10$.
If $m+n \geq 5$ then we will show that
$$m^{2}+n^{2}-m n-m-n \geq 2$$
which is equivalent to
$$(m-n)^{2}+(m-1)^{2}+(n-1)^{2} \geq 6$$
If at least one of the numbers $m, n$ is greater or equal to 4 then $(m-1)^{2} \geq 9$ or $(n-1)^{2} \geq 9$ hence the desired result holds. As a result, it remains to check what happens if $m \leq 3$ and $n \leq 3$. Using the condition $m+n \geq 5$ we have that all such pairs are $(m, n)=(2,3),(3,2),(3,3)$.
All of them satisfy the condition and also the inequality $m^{2}+n^{2}-m n-m-n \geq 2$, thus we have the desired result.

Alternative solution by PSC. The problem equivalently asks for to find the minimum value of
$$A=(m+n)\left(m^{2}+n^{2}-m n-m-n\right)$$
given that $(m+n)\left(m^{2}+n^{2}-m n-m-n\right)>0$. If $m=n$, we get that $m>2$ and
$$A=2 m\left(m^{2}-2 m\right) \geq 6\left(3^{2}-6\right)=18$$
Suppose without loss of generality that $m>n$. If $n=1$, then $m(m+1)(m-2)>0$, therefore $m>2$ and
$$A \geq 3 \cdot(3+1) \cdot(3-2)=12$$
If $n \geq 2$, then since $m \geq n+1$ we have
$$A=(m+n)\left(m(m-n-1)+n^{2}-n\right) \geq (2 n+1)\left(n^{2}-n\right) \geq 5\left(2^{2}-2\right)=10$$
In all cases $A \geq 10$ and the equality holds if $m=n+1$ and $n=2$, therefore if $m=3$ and $n=2$. It follows that the maximum $k$ is $k=10$.