He estado corriendo en círculos con esta por un tiempo ahora.
Parece que la única solución es $(n,m,k)=(2,3,2)$ pero no sé cómo demostrarlo.
Cosas que he notado: WLOG $n\geq m$ vemos que $k^2$ es un múltiplo de a $m!$. Tengo la sensación de que esta podría ser la clave; tal vez hay una restricción en las plazas y factoriales que sólo es posible a $n=k=2$... he intentado manipular las cosas, la única potencialmente útiles expresión que se me ocurrió fue:
$$(n!-1)(m!-1)=1+k^2$$
He tratado de aritmética modular en ambos lados para obtener algunas condiciones adicionales, pero nada útil. Tal vez podríamos hacer uso de $m!n!<(m+n)!$ a obligado a $k^2?$ (dudo que si desde el lado derecho sopla demasiado rápido).
No sé si alguna de esta información es útil, aunque.