Solution from PuzzlingCane First let us show that $k=2$ is impossible. Assume $k=2$. Looking at the equation in $\pmod 7$ gives $5^m=a^2 \pmod 7$ It is easy to show that $5^m$ is congruent to a quadratic residue $\pmod 7$ if and only if $m$ is even. Looking at the equation in $\pmod 3$ gives $(-1)^m+1=a^2 \pmod 3$ which is a contradiction when $m$ is even. Thus we have ruled out $2$ as the answer. Now let us show that $k=3$ is impossible. Assume $k=3$. Looking at the equation in $\pmod 7$ gives $5^m=a^3 \pmod 7$ We can see that $5^m$ is congruent to a cubic residue $\pmod 7$ if and only if $3$ divides $m$. Let $m=3\ell$. Looking at the equation $\pmod 9$ gives $5^{3\ell}+4=a^3 \pmod 9$, and $(5^3)^{\ell}+4=a^3 \pmod 9$ or $(-1)^{\ell}+4=a^3 \pmod 9$ This has no solutions because the cubic residues $\pmod 9$ are $0, \pm 1 \text{ and } 4\pm 1\neq 0, \pm 1$. Thus we have ruled out $3$ as the answer. $k=4$ is obviously impossible given $k=2$ is impossible because if $5^m+63n+49=a^4$, if we write $a'=a^2$ then we have $5^m+63n+49=\left(a'\right)^2$ which we already showed is impossible. $(m,n,a,k)=(1,3,3,5)$ satisfies the equality, hence the minimum value of $k$ is $5$.

Suppose $k=2$ Then $m$ is even because $5^m \equiv a^2 \equiv 1,2,4 \pmod{7}$ and so $m \equiv 0,2,4 \pmod{6}$ Now $\pmod{9}$ gives $25^x \equiv a^2-4 \pmod{9}$, however $a^2 -4 \equiv 5,6,8,2$ and $25^x \equiv 1,4,7 \pmod{9}$ so no solution for $k=2$ Therefore try $k=3$ Now, $\pmod{7}$ implies $m \equiv 0 \pmod{3}$ and $\pmod{9}$ implies $a^3 -4 \equiv (-1)^x$ so $a^3 \equiv 3,5 \pmod{9}$ no solution. Therefore, try $k=5$ (it isn't $k=4$ because write $b = a^2$ and then we get $b^2$ but then it's a square and we can't have a square) $(m,n,a,k) = (1,3,3,5)$. Done. @above thanks for the snipe xd

My solution from the exam. $Answer:5$. The example: $m=1$ $n=3$ $a=3$ $k=5$ We will show that $k=2,3,4$ have no solution. i)Assume that $k=2$. $5^m+63n+49 =a^2$ $(-1)^m+1 \equiv a^2$ $(-1)^m+1 \equiv a^2$ $\pmod{3}$ Note that m is odd. $5^m \equiv a^2$ $\pmod{7}$ $5^m \equiv 5,6,3$ $\pmod{7}$ and $a^2 \equiv 0,1,2,4$ $\pmod{7}$ Contradiction ii)Assume that $k=3$. $5^m+63n+49=a^3$ By $\pmod{7}$ we get $5^m \equiv a^3$ $\pmod{7}$ $5^m \equiv 5,4,6,2,3,1$ $\pmod{7}$ and $a^3 \equiv 0,1,6$ $\pmod{7}$ So $3|m$. Let $m=3r$. By $\pmod{9}$ $(-1)^r+4 \equiv a^3$ $\pmod{9}$ $(-1)^r+4 \equiv 3,5$ $\pmod{9}$ and $a^3 \equiv 0,1,8$ $\pmod{9}$ Contradiction iii)Assume that $k=4$. $k=2$ doesn't have a solution so $k=4$ doesn't have solution, too.