We can proceed as follows. Let $p$ be the probability that we flip a head, and $q=1-p$ the probability that we flip tails. Let us search for the probability that we do NOT have at least $k$ heads in a row at some point after $n$ flips, which we will denote $P(n,k)$.
Given a sequence of coin tosses (of length at least $k)$ which does not have $k$ heads in a row, the end of sequence must be a tail followed by $i$ heads, where $0\leq i. We will let $P(n,k,i)$ denote the probability that a string of length $n$ has less than $k$ heads AND ends with $i$ heads. Clearly $P(n,k)=\sum P(n,k,i)$. (Also note that we can still work with $n by treating a string of just $i$ heads as being in the class $(n,k,i)$).
Suppose we have a series of $n$ coin flips, with no more than $k$ heads, and we are in the class $(n,k,i)$. What can happen if we flip the coin once more? If we get tails, we end up in class $(n+1,k,0)$, which happens with probability $q$, and if we get heads, we end up in the class $(n,k,i+1)$ which happens with probability $p$. The only caveat is that if $i=k-1$, our string will have $k$ heads in a row if the next run is a head.
From this, and using the fact that the $(n+1)$st flip is independent of the flips that came before, we can calculate:
$P(n+1,k,i+1)=pP(n,k,i) \qquad 0\leq i
and so $P(n,k,i)=p^iP(n-i,k,0) \qquad 0\leq i
This could have been seen more directly by noting that the only way to be in the class $(n,k,i)$ is to have a string in class $(n-i,k,0)$ and to then have $i$ heads in a row, which happens with probability $p^i$. This means that we only need to use things of the form $P(n,k)$ and $P(n,k,0)$ in our calculations.
By similar reasoning about how strings come about, we have $P(n+1,k,0)=qP(n,k)=q\sum_{i=0}^{k-1} P(n,k,i)=q\sum_{i=0}^{k-1} p^iP(n-i,k,0).$
This gives us a nice linear recurrence relation for $P(n,k,0)$ very similar to the one for the $k$-Fibonacci numbers, and dividing by $q$, we see that $P(n,k)$ satisfies the same recurrence. Adding the initial condition $P(n,k)=1$ if $n allows us to easily generate the values we need.
Moreover, if we multiply our recurrence by $p^{-(n+1)}$, we get a slightly simpler recurrence for $Q(n+1,k,0)=p^{-(n+1)}P(n+1,k,0)$, namely
$Q(n+1,k,0)=\frac{q}{p} \sum_{i=0}^{k-1} Q(n-i,k,0).$
When $p=q$, this becomes the recurrence for the $k$-Fibonacci numbers.