Let $p(m,h;\,n,k)$ be the probability of turning up a run of $k$ or more heads given:
- $m$ coins out of $n$ have already been flipped and no runs of $\geq k$ heads have occurred
- the last $h$ coins flipped have turned up heads; either no flip preceded this run of $h$ heads or the preceding flip was tails
Then we have the implications:
- If we've completed a run of $k$ flips on the $m$'th flip: $$h = k \implies p(m,h;\,n,k) = 1$$
- If we no longer have sufficient tosses remaining to make a run of length $\geq k$: $$(n-m) + h < k \implies p(m,h;\,n,k) = 0$$
- Otherwise, we partition the event space: the $(m+1)$'th flip is heads with probability $p_{m+1}$ or tails with probability $q_{m+1} \triangleq 1 - p_{m+1}$: $$(n-m) + h \geq k \implies p(m,h;\,n,k) = p_{m+1}p(m+1,h+1;\,n,k) + q_{m+1}p(m+1,0;\,n,k)$$
The probability of a run existing of length $\geq k$ in $n$ flips, which we denote $p_{\text{run}\geq k}$ is given by $$p_{\text{run}\geq k} = p(0,0;\,n,k)$$ and we can recursively substitute in $p$ values for larger values of $m$ and $h$ until the expression is complete. Note that this process runs in $O(n^2)$ [i.e. quadratic] time.
Example
Given $n = 6,\,k = 3$, and omitting the latter two parameters of $p$ for brevity:
$$p_{\text{run}\geq 3} = p(0,0)$$
$$\begin{array}{rcll}\mathbf{Function} & {} & \mathbf{Expression} & \mathbf{Condition} \\
p(0,0) & = & p_1p(1,1) + q_1p(1,0) & (6^{=\,n}-0^{=\,m}) + 0^{=\,h} \geq 3^{=\,k} \\\hline
p(1,0) & = & p_2p(2,1) + q_2p(2,0) & (6^{=\,n}-1^{=\,m}) + 0^{=\,h} \geq 3^{=\,k} \\
p(1,1) & = & p_2p(2,2) + q_2p(2,0) & (6^{=\,n}-1^{=\,m}) + 1^{=\,h} \geq 3^{=\,k} \\\hline
p(2,0) & = & p_3p(3,1) + q_3p(3,0) & (6^{=\,n}-2^{=\,m}) + 0^{=\,h} \geq 3^{=\,k} \\
p(2,1) & = & p_3p(3,2) + q_3p(3,0) & (6^{=\,n}-2^{=\,m}) + 1^{=\,h} \geq 3^{=\,k} \\
p(2,2) & = & p_3p(3,3) + q_3p(3,0) & (6^{=\,n}-2^{=\,m}) + 2^{=\,h} \geq 3^{=\,k} \\\hline
p(3,0) & = & p_4p(4,1) + q_4p(4,0) & (6^{=\,n}-3^{=\,m}) + 0^{=\,h} \geq 3^{=\,k} \\
p(3,1) & = & p_4p(4,2) + q_4p(4,0) & (6^{=\,n}-3^{=\,m}) + 1^{=\,h} \geq 3^{=\,k} \\
p(3,2) & = & p_4p(4,3) + q_4p(4,0) & (6^{=\,n}-3^{=\,m}) + 2^{=\,h} \geq 3^{=\,k} \\
p(3,3) & = & 1 & 3^{=\,h} = 3^{=\,k} \\\hline
p(4,0) & = & 0 & (6^{=\,n}-4^{=\,m}) + 0^{=\,h} < 3^{=\,k} \\
p(4,1) & = & p_5p(5,2) + q_5p(5,0) & (6^{=\,n}-4^{=\,m}) + 1^{=\,h} \geq 3^{=\,k} \\
p(4,2) & = & p_5p(5,3) + q_5p(5,0) & (6^{=\,n}-4^{=\,m}) + 2^{=\,h} \geq 3^{=\,k} \\
p(4,3) & = & 1 & 3^{=\,h} = 3^{=\,k} \\\hline
p(5,0) & = & 0 & (6^{=\,n}-5^{=\,m}) + 0^{=\,h} < 3^{=\,k} \\
p(5,1) & = & 0 & (6^{=\,n}-5^{=\,m}) + 1^{=\,h} < 3^{=\,k} \\
p(5,2) & = & p_6p(6,3) + q_6p(6,0) & (6^{=\,n}-5^{=\,m}) + 2^{=\,h} \geq 3^{=\,k} \\
p(5,3) & = & 1 & 3^{=\,h} = 3^{=\,k} \\\hline
p(6,0) & = & 0 & (6^{=\,n}-6^{=\,m}) + 0^{=\,h} < 3^{=\,k} \\
p(6,3) & = & 1 & 3^{=\,h} = 3^{=\,k}
\end{array}$$
Back-substituting yields: $$\begin{split}p_{\text{run}\geq 3} =
{p_1}{p_2}{p_3} + {p_1}{p_2}{q_3}{p_4}{p_5}{p_6} + {p_1}{q_2}{p_3}{p_4}{p_5} + {p_1}{q_2}{q_3}{p_4}{p_5}{p_6} + {} \\
{q_1}{p_2}{p_3}{p_4} + {q_1}{p_2}{q_3}{p_4}{p_5}{p_6} + {q_1}{q_2}{p_3}{p_4}{p_5} + {q_1}{q_2}{q_3}{p_4}{p_5}{p_6}\end{split}$$
As for getting a closed-form expression when $p_i = f(i)$, you may want to play around with various values of $n$ and $k$ and see if the sequence of coefficients in the multinomial appears somewhere in OEIS. (Note that if you do this, you'll probably want to express the multinomial solely in terms of $p_i$'s [not $q_i$'s], since the multinomial exhibits no symmetries in terms otherwise.)
