Solution: Vertex $S$ can be colored with any of the $m$ colors, and the color on $S$ cannot appear on the vertices of the polygon $A_{1} A_{2} \cdots A_{n}$. The problem is then reduced to coloring the vertices of the polygon with $m-1$ colors, ensuring that adjacent vertices have different colors. Let there be $a_{n}$ ways to do this. Then,
$$a_{3}=(m-1)(m-2)(m-3) .$$

For $n>3$, consider the recurrence relation for $a_{n}$. If starting from $A_{1}$, then $A_{1}$ has $(m-1)$ ways to be colored, and $A_{2}, \cdots, A_{n-1}$ each have $(m-2)$ ways to be colored, and finally to $A_{n}$, if only requiring $A_{n}$ to be different from $A_{n-1}$, there are still $(m-2)$ ways to color it. Thus, there are
$$(m-1)(m-2)^{n-1}$$

ways in total. However, this calculation can be divided into two categories: one where $A_{n}$ is different from $A_{1}$, which meets the requirement and is exactly $a_{n}$ ways; the other where $A_{n}$ is the same as $A_{1}$, which does not meet the requirement, but by merging $A_{n}$ and $A_{1}$ into one point, we get $a_{n-1}$ ways. Therefore,
$$\left\{\begin{array}{l} a_{n}+a_{n-1}=(m-1)(m-2)^{n-1},(n>3) \\ a_{3}=(m-1)(m-2)(m-3) . \end{array}\right.$$

Transforming and recursively,
$$\begin{array}{l} a_{n}-(m-2)^{n}=-\left[a_{n-1}-(m-2)^{n-1}\right] \\ =(-1)^{2}\left[a_{n-2}-(m-2)^{n-2}\right] \\ =\cdots \cdots \\ =(-1)^{n-2}(m-2) \\ =(-1)^{n}(m-2) . \end{array}$$

Thus, $a_{n}=(m-2)\left[(m-2)^{n-1}+(-1)^{n}\right]$.
Therefore, the total number of coloring methods for the entire pyramid is
$$N=m(m-2)\left[(m-2)^{n-1}+(-1)^{n}\right] \text {. }$$

In particular, for $n=4, m=5$, we get
$$N=5 \cdot 3\left(3^{3}+1\right)=420 \text {. }$$

Here, we see the shadow of an old problem: dividing a circular surface into $n(n \geqslant 2)$ sectors, denoted as $S_{1}, S_{2}, \cdots, S_{n}$. Each sector can be colored with one of the three different colors: red, white, and blue, with the requirement that adjacent sectors have different colors. How many coloring methods are there?