In your "$k$ fair $n$-sided dice" setup, imagine $n=k=2$ for simplicity: you're flipping two coins, each of which can come up either heads or tails. There are three possible outcomes if order doesn't matter, namely HH, HT, TT, while your formula would give $2^2/2! = 2$.
The problem is that among the "ordered" outcomes HH, HT, TH, TT, the outcomes HH and TT are only coming up once, hence dividing by $2!$ to fix the "overcount" of those outcomes (which is correct for HT/TH) is actually causing an undercount.
One way to address your problem is to use the Inclusion-Exclusion Principle, which will allow us to avoid doing case work. Let's look at your example.
Since there are $36$ possible outcomes for each roll of a pair of six-sided dice, there are $36^5$ possible outcomes for five rolls of a pair of dice. From these, we must exclude those outcomes in which a sum of $3$, a sum of $4$, or a sum of $8$ is missing. We want to find
$$|A \cap B \cap C| = 36^5 - |A' \cup B' \cup C'|$$
By the Inclusion-Exclusion Principle,
$$|A' \cup B' \cup C'| = |A'| + |B'| + |C'| - |A' \cap B'| - |A' \cap C'| - |B' \cap C'| + |A' \cap B' \cap C'|$$
You observed that there are two ways to obtain a sum of $3$, three ways to obtain a sum of $4$, and five ways to obtain a sum of $8$.
$|A'|$: Since there are two ways to obtain a sum of $3$, there are $36 - 2 = 34$ ways to not obtain a sum of $3$ on each of the five rolls. Hence, $|A'| = 34^5$.
$|B'|$: Since there are three ways to obtain a sum of $4$, there are $36 - 3 = 33$ ways to not obtain a sum of $4$ on each of the five rolls. Hence, $|B'| = 33^5$.
$|C'|$: Since there are five ways to obtain a sum of $8$, there are $36 - 5 = 31$ ways to not obtain a sum of $8$ on each of the five rolls. Hence, $|B'| = 31^5$.
$|A' \cap B'|$: Excluding sums of $3$ and $4$ eliminates $2 + 3 = 5$ possible outcomes for each of the five rolls. Hence, $|A' \cap B'| = (36 - 5)^5 = 31^5$.
$|A' \cap C'|$: Excluding sums of $3$ and $8$ eliminates $2 + 5 = 7$ possible outcomes for each of the five rolls. Hence, $|A' \cap C'| = (36 - 7)^5 = 29^5$.
$|B' \cap C'|$: Excluding sums of $4$ and $8$ eliminates $3 + 5 = 8$ possible outcomes for each of the five rolls. Hence, $|A' \cap B'| = (36 - 8)^5 = 28^5$.
$|A' \cap B' \cap C'|$: Excluding sums of $3$, $4$, and $8$ eliminates $2 + 3 + 5 = 10$ possible outcomes for each of the five rolls. Hence, $|A' \cap B' \cap C'| = (36 - 10)^5 = 26^5$.
By the Inclusion-Exclusion Principle, the number of outcomes in which sums of $3$, $4$, and $8$ all appear when five dice are rolled is
$$36^5 - 34^5 - 33^5 - 31^5 + 31^5 + 29^5 + 28^5 - 26^5$$
Best Answer
Note that the Wikipedia article talks about the probability of counts for each side of a $k$-sided dice rolled $n$ times. When you roll a die, its chances of landing in each of $1-6$ is equiprobable, and the multinomial coefficient will help to give the probability for a particular pattern of throws.
For example, a pattern of $2,1,2,1,1,0,1,2,$ will have a probability of $\dfrac{\dbinom{10}{2,1,2,1,1,0,1,2}}{6^{10}}$
Stars and bars instead gives all possible ways of filling $1-6$, but these are not equiprobable, eg you can understand that if you roll a die $10$ times, getting all ten as $6's$ is much less probable than a more even distribution