This long remark consists only of a small progress on OP's question.
Under the assumption that $H$ is normal and $S$ generates $G$ as a monoid, the answer is yes with bound $k(d) := d^2 - d + 1$. This follows from a classical combinatorial result of Schreier [1, Proposition I.3.7].
These ideas of Schreier go back to 1927 and already establish [2, Lemma 3.4] of Shalev and Weigreich (1992).
For $S$ a subset of a group $G$ and $n \in \mathbb{N}_{\ge 0}$, we denote by $S^{\le n}$ the set of elements of $G$ which can be written as product of at most $n$ elements of $S$. The monoid $S^{\ge 0} := \bigcup_{n \ge 0}S^{ \le n}$ is the submonoid of $G$ generated by $S$.
Example 1. Let $G = F(a, b)$ be the free group with basis $\{a, b\}$. Let $S_{m, n, p} = \{a, a^{-n}b, b^{-m}a^{-1}, a^pb^{-1}\}$ with $m,n, p \in \mathbb{N}_{\ge 0}$. Then $G = S_{m ,n, p}^{\ge 0}$ whereas $G \supsetneq \{a, b\}^{\ge 0}$.
Example 2. Let $G$ be a finite group. Then $G = S^{\ge 0}$ for every generating subset $S$ of $G$.
Claim. Let $G$ be a group and let $H$ be a normal subgroup of finite index $d$ in $G$. Let $S \subseteq G$ be such that $G = S^{\ge 0}$. Then $H$ is generated, as a group, by some subset of $S^{\le k(d)}$.
We will use the following lemma.
Lemma. Let $G$ be a finite group. Then $G = S^{\le \vert G \vert - 1}$ for every generating subset $S$ of $G$.
Proof of the lemma. In the connected Cayley graph of the monoid $G$ with respect to $S$, every path of length at least $\vert G \vert$ which connects $1$ to $g \in G$ contains a loop. As loops represent the trivial element of $G$, any such path can be turned into a shorter path connecting $1$ to $g$.
Proof of the claim. Applying the previous lemma to $G/H$ and the image of $S$ in $G/H$, we find a transversal $T$ of $H$ in $G$ such that $1 \in T \subseteq S^{\le d - 1}$.
Using the ideas of the proof of [1, Propositions I.3.7], we infer that $H$ is generated, as a monoid, by elements of the form $\gamma(st)$ with $s \in S, t \in T$,
where $\gamma(g) = g \overline{g}^{-1}$ and $\overline{g} \in T$ is defined through $Hg = H \overline{g}$ for $g \in G$. Indeed, as we have $H = \{\gamma(g) \, \vert \, g \in G\}$ ($T$ is a transversal containing $1$) and $\gamma(gs) = \gamma(g)\gamma(\overline{g}s)$ for every $g \in G, s \in S$ (use the identity $\overline{\overline{g}s} = \overline{gs}$), we deduce that $\gamma(g)$ is a product of elements of the form $\gamma(ts)$ if $g \in S^{\ge 0}$, which holds for every $g \in G$ by assumption. Since $H$ is also generated, as a group, a by elements of the form $\overline{ts}^d, \gamma(ts)\overline{ts}^d = ts \overline{ts}^{d - 1}$, the result follows.
[1] R. Lyndon and P. Schupp, "Combinatorial Group Theory", 1977.
[2] P. Shalev and P. Wagreich, "Growth Rates, Zp-Homology, and Volumes of Hyperbolic 3-Manifolds", 1992