Clearly $k\ne 1,2$ due to modulo $3$. For $k=3$, we have $2+3^{m-1}=3^{n-1}$ which is impossible unless $(m,n,k)=(1,3,2)$ via modulo $3$. For $k=4$, we have $8+3^{m-1}=3^{n-1}$ which is again impossible unless $(m,n,k)=(1,3,4)$ via modulo $3$. For $k=5$, a reasoning along the similar lines yields no solutions. For $k=6$, we have $240+3^{m-1}=3^{n-1}$. Unless $m-1=1$, we have a contradiction via modulo $9$. Thus $(m,n,k)=(2,6,6)$ is another solution.

Via modulo $7$, we find $m\equiv n\pmod{6}$. Moreover, $m\equiv n\pmod{4}$ via modulo $5$. Hence, $m\equiv n\pmod{12}$. By Fermat, $3^{12}\equiv 1\pmod{13}$. Consequently, $13\mid k$, thus $k\ge 13$. This, in turn, yields $11\mid 3^{n-m}-1$ and thus $m\equiv n\pmod{5}$. Consequently, $60\mid m-n$. This time, using modulo $61$ we find $k\ge 61$. We now switch gears to power of two dividing both sides. Using lifting the exponent, we have \[ v_2\left(3^{n-m}-1\right) = v_2(2)+v_2(4) + v_2(n-m)-1 = 2+v_2(m-n). \]On the other hand, using $k\ge 61$, \[ v_2(k!)\ge \frac{k-1}{2} + \frac{k-1}{4}+\frac{k-1}{8} + \frac{k-1}{16} + \frac{k-1}{32}. \]Hence, \[ v_2(n-m)\ge v_2(k!)-2 > \frac{k}{2} + \frac{k}{4} + \frac{k}{8} = \frac{7k}{8}\implies n-m>2^{v_2(n-m)}>2^{7k/8}. \]