The answer is **yes**, with $k = 2d - 1$ as a sharp upper bound. 

This follows from a classical combinatorial result of Otto Schreier known as [Schreier's lemma](https://en.wikipedia.org/wiki/Schreier%27s_lemma) [1, Proof of Proposition I.3.7].
These ideas of Otto Schreier go back to 1927 and already establish [2, Lemma 3.4] of Peter Shalen and Philip Wagreich 
(1992), that is, they are sufficient to show that $2d - 1$ is an upper bound when $S = S^{-1}$. 
In this case, the upper bound $2d - 1$ was furthermore proved to be sharp by Peter Shalen and Philip Wagreich [2, Remark 3.5].

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$. 

> **Claim.** Let $G$ be a group and let $H$ be a subgroup of finite index $d$ in $G$. Let $S$ be a generating subset of $G$. 
Then $H$ is generated by a subset of $S^{\le 2d -1 }$.

The proof of the above claim is a variation on [2, Proof of Lemma 3.4].
We shall rely on the following key fact, which is certainly well-known: there is a spanning sub-tree of the Schreier graph of $H$ in $G$ with respect to $S$, endowed with an "affluent" labeling: the edges in every edge path joining the root to a leaf are labelled by the element of $S$, as opposed to elements of $S \cup S^{-1}$ in the original proof. 

**Definition.** Let $G$ be a free group with basis $S$ and let $H$ be a subgroup of $G$. The *[Schreier coset graph](https://en.wikipedia.org/wiki/Schreier_coset_graph)* $\operatorname{Schreier}_{G, S}(H)$ of $G$ in $H$ with respect to $S$ is the directed and labelled graph whose vertices are the right cosets $Hg$ for $g \in G$ and whose edges are the pairs $(Hg, Hgs)$ with $g \in G$ and $s \in S$. We say that $s$ is the *label* of the edge $(Hg, Hgs)$.

The above definition coincides with the covering of a bouquet of circles labelled by the elements of $S$ considered in the proof of [2, Lemma 3.4].

> **Lemma 1.** Let $G$ be a free group with basis $S$, let $H$ be subgroup of finite index $d$ in $G$. Let $\Gamma = \operatorname{Schreier}_{G, S}(H)$. 
Then $\Gamma$ is [strongly connected](https://en.wikipedia.org/wiki/Strongly_connected_component), i.e, every pair of vertices can be joined by a directed path. 

> *Proof of Lemma 1.* Let $g \in G, s \in S$. Since $H$ has index $d$ in $G$, there is a smallest integer $n = n(Hg) \in \{1, \dots, d\}$ such that $Hgs^n = Hg$, equivalently, 
$Hgs^{-1} = Hgs^{n - 1}$. Consider now two vertices $Hg$ and $Hg'$ with $g, g' \in G$ and write $g^{-1}g'$ as a word on $S \cup S^{-1}$. 
It is sufficient prove that $Hg$ and $Hg'$ are connected by a directed path if the length of $w$ is $1$, as the result follows by immediate induction.
If $w = s \in S$, the result is obvious. If $w = s^{-1}$ for some $s \in S$, then the directed path defined by the sequence of vertices $Hg, Hgs, \dots, Hgs^{n(Hg)-1} = Hgs^{-1}$ joins $Hg$ to $Hg' = Hgs^{-1}$.

> **Lemma 2.** Let $G$ be a free group with basis $S$, let $H$ be subgroup of finite index $d$ in $G$. Let $\Gamma = \operatorname{Schreier}_{G, S}(H)$. 
Then for every vertex $v$ of $\Gamma$, there is an *affluent* directed spanning tree $T$ of $\Gamma$ rooted at $v$, i.e., $T$ is a directed tree such that every leaf of 
$T$ can be connected to $v$ by a directed path starting from $v$.

> *Proof of Lemma 2.* Since $\Gamma$ is finite, we can find a maximal affluent subtree $T$ of $\Gamma$ rooted at $v$. It only remains to show that $Hg$ is vertex of $T$ for every 
$g \in \Gamma$. Reasoning by contradiction, we assume that there is $g \in G$ such that $Hg$ is not a vertex of $T$. Let $p$ be a directed path joining $Hg$ to $T$ with shortest length. (Such a path exists by Lemma 1). Adjoining $p$ to $T$ results in a larger affluent subtree, which contradicts the maximality of $T$. 

We are now in position to prove the main claim.

> *Proof of the Claim.* We can assume, without loss of generality, that $G$ is a free group with basis $S$. By [1, Proposition III.3.1], the subgroup $H$ identifies with the fundamental group of $\Gamma = \operatorname{Schreier}_{G, S}(H)$ with base point $H = H \cdot 1$. Let $T$ be an affluent spanning tree of $\Gamma$ rooted at $H$ given by Lemma 2. 
For $v$ a vertex of $\Gamma$, we denote by $p_v$ 
the unique directed path joining $H$ to $v$ within $T$. Then $H$ is generated by the homotopy classes of the loops $\gamma(Hg, s) = p_{Hg} \cdot s \cdot p_{Hgs}^{-1}$ with $g \in G$ [1, Proof of Proposition III.2.1]. 
Now let $q_{Hg}$ denote a directed path from $Hgs$ to $Hg$ in $\Gamma$ of length at most $d$. 
Then $H$ is also generated by the loops $\gamma(Hg, s) \cdot p_{Hgs} \cdot q_{Hg} =  p_{Hg} \cdot s \cdot q_{Hg}$ and $p_{Hgs} \cdot q_{Hg}$ for $g \in G, s \in S$. As the latter generators are words over $S$ of length at most $2d - 1$, the proof is complete. 

---

[1] R. Lyndon and P. Schupp, "Combinatorial Group Theory", 1977.   
[2] P. Shalen and P. Wagreich, "Growth Rates, Zp-Homology, and Volumes of Hyperbolic 3-Manifolds", 1992