The existence of an algebra homomorphism between $\mathcal{M}_n({\mathbb{K}})$ and $\mathcal{M}_s(\mathbb{K})$ implies $n | s$

Any $M_s(K)$-module becomes an $M_n(K)$-module via pullback under the the map $\Phi$. So, consider $K^s$ as the tautological $M_s(K)$-module. This is also a $M_n(K)$-module. But $M_n(K)$ is semisimple, and up to isomorphism its only simple module is $K^n$. As $\Phi$ is a $K$-algebra map, then $K^n$ also has dimension $n$ as a $K$-vector space, even when viewed as a $K^n$-modules. It must be a direct sum of $r$ simple $M_n(K)$-modules. Via a dimension count $rn=s$, so $n\mid s$.

The existence of $P$ is essentially the Noether-Skolem theorem. We can split up $K^s=N_1\oplus\cdots\oplus N_r$ where the $N_j$ are simple $M_n(K)$-modules. So we can choose a basis of $K^s$ so that $$\Phi=\pmatrix{\Phi_1&0&\cdots&0\\0&\Phi_2&\cdots&0\\\vdots&\vdots &\ddots&\vdots\\0&0&\cdots&\Phi_r}$$ with respect to this basis. Each $\Phi_i$ is a $K$-automorphism of $M_n(K)$ which is an inner automorphism due to Noether-Skolem.

Not sure some "bachelor level" solution is at hand. What is stated in the text ( not in the title) is nothing less than Noether-Skolem in the particular case $n=s$.

Just for fun, let's show that $n\mid s$ without modules, but with determinants. Consider a morphism $\Phi$ from $M_n(\mathbb{K})$ to $M_s(\mathbb{K})$. Denote by $\Delta$ the composition $\det \circ \Phi$. It takes conjugate matrices in $M_n(\mathbb{K})$ to the same element in $\mathbb{K}$. Let $\alpha \in \mathbb{K}$, and $D_{\alpha}$ a diagonal matrix with one element on the diagonal $\alpha$ and the rest $1$. Note they are all conjugate ($n$ of them). Now, $\Delta(D_{\alpha})$ is a polynomial expression in $\alpha$, denote it by $P_(\alpha)$, with coefficients in $\mathbb{K}$. Moreover, since the $n$ matrices of type $D_{\alpha}$ have product $\alpha \cdot I_n$, we have $P(\alpha)^n = \det (\alpha \cdot I_s) = \alpha^s$.

Assume for a moment that $\mathbb{K}$ is infinite. Since a polynomial function on $\mathbb{K}$ comes from a unique polynomial, by considering degrees in the above equality we get $n\mid s$.

We can get away with the hypothesis $\mathbb{K}$ infinite by realizing that a morphism from $M_n(\mathbb{K})$ to $M_s(\mathbb{K})$ gives morphisms from $M_n(\mathbb{ K'})$ to $M_s(\mathbb{K'})$ for any field extension $\mathbb{K'}$ of $\mathbb{K}$.

We do not need the full strength of Noether-Skolem here; as per Lord Shark's solution, we only need to show that any $k$-automorphism $\phi: M_n (k) \to M_n (k)$ is of the form $\phi(X) = TXT^{-1}$ for some $T \in M_n (k)$.

This follows from the fact that $M_n (k)$ is a semisimple algebra whose only simple module, up to isomorphism, is $k^n$ with the standard action of $M_n (k)$. Suppose this fact. We may construct a "twisted" $M_n (k)$ action on $k^n$ by declaring $X \cdot v := \phi(X)(v)$ for $X\in M_n (k)$ and $v\in k^n$. This twisted representation of $M_n (k)$ must be isomorphic to the standard representation of $M_n (k)$, hence there exists a module isomorphism $$T: k^n (\text{standard}) \to k^n (\text{twisted})$$ In particular, for any $X\in M_n (k)$ and $v \in k^n$, we have $$\phi(X)(Tv) = x \cdot (Tv) = T(Xv) \implies (T^{-1} \phi(X) T)v = Xv$$ and thus $T^{-1} \phi(X) T = X$ for all $X\in M_n (k)$, i.e. $\phi(X) = TXT^{-1}$.