Why is complete strong induction a valid proof method and not need to explicitly proof the base cases?

A valid proof by complete induction includes a uniform proof for all $k$ of the inferences listed below. As such it necessarily includes a proof ($\rm\color{#0a0}{vacuous}$) of the base case $\color{#c00}{\,P(0)}.\,$ See the schema below.

$$\begin{align} \color{#0a0}{\bbox[3px,border:2px solid #0a0]{\phantom{:}}}\Rightarrow\,\color{#c00}{ P(0)}\\ P(0)\Rightarrow\, P(1)\\ P(0),P(1)\Rightarrow\, P(2)\\ \vdots\qquad\ \ \ \ \\ P(0),P(1),\ldots,P(k-1)\,\Rightarrow\,P(k)\\ \end{align}\qquad\qquad\qquad\qquad\ \ $$

While a valid inductive proof necessarily implies a proof of $\,\color{#c00}{P(0)},\,$ this may not occur explicitly. Rather, it may be a special case of a much more general implication derived in the proof. For example, in many such proofs the natural base case(s) is not a single number but rather a much larger set. Let's examine a simple induction where the base cases are all odd naturals.

If $n\ge\color{#c00}1$ is an integer then $\,n = 2^{\large i} j\, $ for some odd $j$ and some integer $i\ge 0.\,$ For if $n$ is odd then $n = 2^0 n,\,$ else $\,n = 2k\,$ for $\,1 \le k < n\,$ so induction $\,\Rightarrow k = 2^{\large i} j,\,$ so $\, n = 2k = 2^{\large i+1} j.\ \ $ QED

Here the base case $\color{#c00}{P(1)}$ is not explicitly proved. Instead it is a special case of the more general inference that $\,n\,$ odd $\,\Rightarrow\, n = 2^0 n.\,$ In such factorization (decomposition) problems the natural base cases are all irreducibles (and units) - not only the $\rm\color{#c00}{least}$ natural in the statement, e.g. in the proof of existence of prime factorizations of integers $\,n > 1,\,$ with base cases being all primes.

Remark $\ $ Ditto for its contrapositive form infinite descent: $\, $ if given a counterexample $\,\lnot P(n)\,$ we can prove there exists a smaller counterexample $\lnot P(k),\ k < n,\,$ then no counterexample exists, else iterating the proof would yield an infinite descending chain of counterexamples, contra $\,\Bbb N\,$ is well-ordered. Or, reformulated, if there is a counterexample then, by well order, we can choose a minimal one ("minimal criminal"), contra the proof yields a smaller one.

if we show $ P(m), m<n \implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b \in BaseCases$)

Right, that's exactly correct: if there is nothing smaller than $0$ (as is the case for the natural numbers) then it is vacuously true that:

$$P(m) \text{ holds for any } m<0 \tag{1}$$

So, if you have shown that:

$$\text{for any } n: \text{ if } P(m) \text{ holds for any } m<n, \text{ then } P(n) \tag{2}$$

then in particular you have shown that:

$$\text{ if } P(m) \text{ holds for any } m<0, \text{ then } P(0) \tag{2'}$$

and so we get

$$P(0)$$

by Modus Ponens on $(1)$ and $(2')$

So, there is indeed no need to prove an explicit base case.

That said, think about how in practice you would actually prove $(2)$. Probably, you would be able to show $P(n)$ based on the assumption that there actually are $m<n$ for which we can show that if they all have property $P(m)$, then $P(n)$. But for the edge case of $n=0$, there are no such $m<n$ ... so ... you need to show $P(0)$ by itself!

In other words, in practice, you often do have to treat the base cases as special cases that you prove as base cases after all.

if we show $ P(m), m<n \implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b \in BaseCases$)

It's not clear exactly how one ought to interpret "$P(m), m<n \implies P(n)$", but I think we have agreed that the following formula (shown in the answer by José Carlos Santos) represents the induction step according to the article: $$((\forall m\in\{0,1,2,\ldots,n-1\})\ P(m))\implies P(n).$$

You seem to be looking at this and saying that for the case $n = 0,$ it is equivalent to $$\bot \implies P(n),$$ using $\bot$ as a symbol for something that is always false. This implication is vacuously true. But in fact, a statement of the form $$ (\forall m\in \emptyset)\ P(m) $$ is also vacuously true. That is, it is true because there is no value of $m$ that can make it false. This may be a little more obvious if you write it this way: $$ (\forall m)(m \in \emptyset \implies P(m)). $$

So what the induction step of complete induction actually says in the case $n = 0$ is that $$\top\implies P(0),$$ where $\top$ is always true. If you prove that $\top\implies P(0),$ you have proved $P(0).$

You might question whether the Wikipedia article does a good job of explaining itself, and I would sympathize. It's only an encyclopedia article, however; a self-evident justification for everything may be too much too ask. (Useful inline citations for details such as this are not too much to ask, however, and there is a notice at the top of that section of the article requesting them.)