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 [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, Peter Shalen and Philip Wagreich have proved in addition that $2d - 1$ is a sharp upper bound [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 $\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, 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