First of all, here is a non-combinatorial proof of your identity. We repeatedly apply the recurrence relation $S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)$, each time applying it to the $S(n-1,k)$ part. Here are the first three steps of what I mean:
$$
\begin{align}
S(n,k)
&=S(n-1,k-1)+k\cdot \color{blue}{S(n-1,k)}
\\&=S(n-1,k-1)+k\Big(S(n-2,k-1)+k\cdot \color{blue}{S(n-2,k)}\Big)
\\&=S(n-1,k-1)+k\Big(S(n-2,k-1)+k\cdot \Big(S(n-3,k-1)+k\cdot \color{blue}{S(n-3,k)}\Big)\Big)
\\&=\vdots
\end{align}
$$
If you apply that all the way down, and then distribute all products, the result is exactly $\sum_i k^i S(n-1-i,k-1)$, which is equivalent to the summation in your question.
How can we turn this into a combinatorial proof? Well, we repeatedly applied the identity $S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)$, which itself has a combinatorial proof, so chaining all of those bijections together should give a bijective proof of your identity.
When you do this, here is the bijection that you get. To prove that $S(n,k)=\sum_{i=1}^{} S(i,k)k^{n-1-i}$, we answer the following question:
Given a partition $P$ of $\{1,\dots,n\}$ into $k$ unlabeled parts, define $f(P)$ to be the largest number $j$ such that the numbers $\{1,\dots,j\}$ do not span all $k$ of the parts (i.e., such that some part contains none of $\{1,\dots,j\}$). Given $i\in \{k-1,k,\dots,n-1\}$, for how many partitions does $f(P)=i$?
We will prove that the answer to this is $S(i,k-1)k^{n-1-i}$, so summing over $i$ proves your identity.
If $f(P)=i$, then the numbers $\{1,\dots,i\}$ must span exactly $k-1$ parts. The number of ways to place the numbers $\{1,\dots,i\}$ is therefore $S(i,k-1)$. Then, $i+1$ must be in a different part from each of the numbers in $\{1,\dots,i\}$. Finally, for the $n-1-i$ numbers in $\{i+2,i+3,\dots,n\}$, they must each be independently placed in one of the $k$ parts, which can be done in $k^{n-1-i}$ ways.
Best Answer
Hint: Consider the following algorithm:
You have a list of the $n+m$ numbers and you start with $\{1\}$ as the partition, you start also with a pointer starting at $2$ that is going to increase $n$ times and in each number you have the following decision to make: If the number of blocks is exactly $m,$ you have $m$ options per number. If not, you can decide if you want to append the number to a block or create a new block where the number is going to be the smallest element of the block. When this happens the number of blocks will increase.
As an example and for simplicity, assume $m=2$ and take $n=3.$ We start with $1$ and we place it in a block so $\{1\}$ is what we have. Then $2,$ if we decide to place $2$ in the other block, then we will end up having $2^3$ options for the rest of numbers. If we decide to place $3$ as the smallest element of the new block, we will have $2^2$ options and so on. So we will have $$\sum _{i=0}^{3}2^i=2^4-1=LHS,$$ but of course every partition can be created in this way. There you can check that this is the correspondence $$\underbrace{1^3}_{\{1,2,3,4\},\{5\}}+\underbrace{1^2\cdot 2}_{\{1,2,3,\cdots \},\{4,\cdots \}}+\underbrace{1^1\cdot 2^2}_{\{1,2,\cdots \},\{3,\cdots \}}+\underbrace{ 2^3}_{\{1,\cdots \},\{2,\cdots \}}$$
So, to generalize, consider where do the numbers change, so I would suggest you write the LHS as $$\sum_{d_1+d_2+\cdots +d_m=n}1^{d_1}2^{d_2}\cdots m^{d_m}.$$
Here the $d_i$ represent the frequency of $i$ in the sequence $k$ i.e., $$d_i = |\{j:k_j=i\}|.$$
A way to understand this algorithm is to think about it backwards. Suppose I give you a partition $\pi \vdash [n+m]$ with $m$ blocks. Suppose the blocks are labelled $\pi =\{B_1,\cdots , B_m\}$ where the blocks are ordered by their minimal elements $b_i\in B_i: 1=b_1<b_2<\cdots<b_m\le n+m$. Consider further the consecutive differences of these numbers $d_i=b_{i+1}-b_{i}-1\ (0<i<m)$, $d_m=n+m-b_m.$ Notice that $d_i\ge0$ and $d_1+d_2+\cdots +d_m=n+m-(m-1)-b_1=n$. Notice further that $d_i$ is essentially the number of elements which can be placed arbitrarily in any of the first $i$ blocks, so that there are $i^{d_i}$ ways to perform this.