Cleaning up the notation a bit,
$$b_{m,k}(n) = m\, b_{m,k}(n-2^{\ell(n)}) + k \sum_{j=0}^{\ell(n)-1} [n \,\&\, 2^j = 0] \,b_{m,k}(n - 2^{\ell(n)} + 2^j)$$ where $\&$ is bitwise AND.
$$s_{m,k}(n) = \sum_{j=0}^{2^n-1} b_{m,k}(j)$$
Let $\operatorname{wt}(n)$ be the Hamming weight of $n$, and for an arbitrary polynomial $p(z)$ define $$s_{m,k}^p(n) = \sum_{j=0}^{2^n-1} p(\operatorname{wt}(j)) b_{m,k}(j)$$ This generalises $s_{m,k} = s_{m,k}^{z^0}$. The differences reduce nicely:
$$\begin{eqnarray*}s_{m,k}^p(n) - s_{m,k}^p(n-1)
&=& \sum_{j=2^{n-1}}^{2^n-1} p(\operatorname{wt}(j)) b_{m,k}(j) \\
%&=& \sum_{j=0}^{2^{n-1}-1} p(\operatorname{wt}(2^{n-1} + j)) b_{m,k}(2^{n-1} + j) \\
&=& \sum_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) b_{m,k}(2^{n-1} + j) \\
%&=& \sum_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) \left( m\, b_{m,k}(j) + k \sum_{i=0}^{n-2} [j \,\&\, 2^i = 0] \,b_{m,k}(j + 2^i) \right) \\
&=& m \sum_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) b_{m,k}(j) + k \sum_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) \sum_{i=0}^{n-2} [j \,\&\, 2^i = 0] \,b_{m,k}(j + 2^i) \\
%&=& m s_{m,k}^{E_z p}(n-1) + k \sum_{j=0}^{2^{n-1}-1} \sum_{i=0}^{n-2} [j \,\&\, 2^i = 0] p(\operatorname{wt}(j + 2^i)) b_{m,k}(j + 2^i) \\
%&=& m s_{m,k}^{E_z p}(n-1) + k \sum_{j=0}^{2^{n-1}-1} \operatorname{wt}(j) p(\operatorname{wt}(j)) b_{m,k}(j) \\
&=& m s_{m,k}^{E_z p}(n-1) + k s_{m,k}^{zp}(n-1) \\
\end{eqnarray*}$$ where $E_z$ is the raising operator $(E_z p)(z) = p(z+1)$.
With the base case $s_{m,k}^p(0) = p(0)$, we get $s_{m,k}(n) = (1 + mE_z + kz)^n z^0 \mid_{z=0}$.
Two useful subresults towards the main proof:
Theorem: $(mE_z + kz)^d z^0 \mid_{z=0} = \sum_{i=0}^d \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i} k^{d-i} m^i$ where $\genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i}$ is a Stirling number of the second kind.
By induction.
- In the base case, $d=0$, we have $1 = \genfrac{\lbrace}{\rbrace}{0pt}{}{0}{0}$.
- Note that by repeated application of $E_z z = (z+1)E_z$ we can rewrite $(mE_z + kz)^d$ as $\sum_{i=0}^d k^{d-i} m^i q_{k,m}(z) E_z^m$ where the $q_{k,m}$ are polynomials. Then $(mE_z + kz)^d z^0 \mid_{z=0} = \sum_{i=0}^d \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i} k^{d-i} m^i$ is equivalent to $\forall i \in [0,d]: q_{d-i,i}(0) = \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i}$. Now we multiply on the right to get $$\begin{eqnarray*}(mE_z + kz)^{d+1}
&=& \sum_{i=0}^d k^{d-i} m^i q_{k,m}(z) E_z^m (mE_z + kz) \\
&=& \sum_{i=0}^d k^{d-i} m^{i+1} q_{k,m}(z) E_z^{m+1} + k^{d-i+1} m^i q_{k,m}(z)(z+m) E_z^m \\
\end{eqnarray*}$$ so $q_{k,m}(0) = q_{k,m-1}(0) + k q_{k-1,m}(0)$ $= \genfrac{\lbrace}{\rbrace}{0pt}{}{k+m-1}{m-1} + k \genfrac{\lbrace}{\rbrace}{0pt}{}{k+m-1}{m}$ $= \genfrac{\lbrace}{\rbrace}{0pt}{}{k+m}{m}$.
Theorem: $(\exp(z)-1)^i = \sum_{n \ge i} \frac{i!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i} z^n$
Surely standard. By induction: $(\exp(z)-1)^0 = 1 = \sum_{n \ge 0} \frac{0!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{0} z^n$ checks out, and $$\begin{eqnarray*}\left(\sum_{n \ge i} \frac{i!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i} z^n\right)(\exp(z)-1)
&=& \left(\sum_{n \ge i} \frac{i!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i} z^n\right)\left( \sum_{j \ge 1} \frac{1}{j!} z^j\right) \\
&=& \sum_{n \ge i+1} z^n \sum_{j=1}^n \frac{i!}{(n-j)!j!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n-j}{i} \\
&=& \sum_{n \ge i+1} \frac{i!}{n!} z^n \sum_{j=1}^n \binom{n}{j} \genfrac{\lbrace}{\rbrace}{0pt}{}{n-j}{i} \\
\end{eqnarray*}$$
The inner sum counts pointed partitions of $n$ items into $i+1$ sets, so equals $(i+1) \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i+1}$, completing the proof.
Theorem: $\sum_{n \ge 0} \frac{s_{m,k}(n)x^n}{n!} =
\exp\left(x + m\frac{\exp(kx) - 1}{k}\right)$
For the LHS we have $$\begin{eqnarray*}\sum_{n \ge 0} \frac{s_{m,k}(n)x^n}{n!}
&=& \sum_{n \ge 0} \frac{x^n}{n!} \sum_{d=0}^n \binom{n}{d} \sum_{i=0}^d \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i} k^{d-i} m^i \\
&=& \sum_{n,i,j \ge 0} \frac{1}{n!} \binom{n}{i+j} \genfrac{\lbrace}{\rbrace}{0pt}{}{i+j}{i} x^n m^i k^j
\end{eqnarray*}$$
For the RHS we have \begin{eqnarray*}\exp\left(x + m\frac{\exp(kx) - 1}{k}\right)
&=& \exp\left(x + mx\frac{\exp(kx) - 1}{kx}\right) \\
&=& \sum_{u \ge 0} \frac{x^u}{u!} \left(1 + m\frac{\exp(kx) - 1}{kx}\right)^u \\
&=& \sum_{u,i \ge 0} \frac{x^u}{u!} \binom{u}{i} \left(\frac{m}{kx} \right)^i (\exp(kx) - 1)^i \\
&=& \sum_{u,i \ge 0} \frac{x^u}{u!} \binom{u}{i} \left(\frac{m}{kx} \right)^i \sum_{v \ge i} \frac{i!}{v!} \genfrac{\lbrace}{\rbrace}{0pt}{}{v}{i} (kx)^v \\
&=& \sum_{n,i,j \ge 0} \frac{1}{n!} \binom{n}{i+j} \genfrac{\lbrace}{\rbrace}{0pt}{}{i+j}{i} x^n m^i k^j
\end{eqnarray*}
where the final line uses the substitutions $j = v-i$ and $n = u+j$.
Finally, note that the operator expression for $s_{m,k}$ gives the elegant formulation of the main theorem as $$\exp(x(1 + mE_z + kz)) z^0 \mid_{z=0} = \exp\left(x + m\frac{\exp(kx) - 1}{k}\right)$$
