Fix any probability vector $(p_1,\ldots,p_k)$ and consider $E\subset \{1,\ldots, n\}^k$ such that $$E\subset\left\{(i_1,\ldots,i_k); \sum_{j}^ki_j=n\ \text{and }\ p_j\geq\frac{i_j}{n} \right\}$$
For any element of $E$, we have
$$\sum_{j}^k p_j\log p_j\leq \sum_{j=1}^k \frac{i_j}{n}\log p_j.$$ Therefore $$-n\left(\sum_{j=1}^k-p_j\log p_j \right)\leq \sum_{j=1}^k i_j\log p_j.$$ Exponentiating both sides we get $$\exp\left(-n\left(\sum_{j=1}^k-p_j\log p_j \right)\right)\leq p_1^{i_1}\ldots p_k^{i_k}.$$ For the other hand, we have that $$1=(p_1+\ldots+p_k)^n=\sum_{i_1,\ldots,i_k}\frac{n!}{i_1!\ldots i_k!}p_1^{i_1}\ldots p_k^{i_k}\geq \sum_{(i_1,\ldots,i_k)\in E}\frac{n!}{i_1!\ldots i_k!}\exp\left(-n\left(\sum_{j=1}^k-p_j\log p_j \right)\right),$$ where the first summation is taken over all sequences of nonnegative integer indices $i_1$ through $i_k$ such the sum of all $i_j$ is $n$.
So we get that $$\sum_{(i_1,\ldots,i_k)\in E}\frac{n!}{i_1!\ldots i_k!}\leq\exp\left(n\left(\sum_{j=1}^k-p_j\log p_j \right)\right)\leq e^{n H^*}.$$