Let $a_n$ be the number of strings of length $n$ where every $1$ is followed by at most $k$ zeroes. There are two cases; either the string has a one, or it doesn't. In the former case, the maximal run of zeroes at the end must be of length at most $k$. Therefore, for all $n>k+1$,
$$
a_n = 1+a_{n-1}+a_{n-2}+\dots+a_{n-k-1}
$$
As you said, the base cases are $a_n=2^n$ for $n\le k+1$. (Note the base case $a_0=1$, because there is one valid string of length $0$, namely the empty string).
For example, when $k=0$, the recurrence is $a_n=a_{n-1}+1$, which implies $a_n=n+1$. Also,
$$
f(4,2) = 1+f(3,2) + f(2,2) + f(1,2) =1+8 + 4 + 2 = 15\\
f(5,2) = 1+f(4,2) + f(3,2) + f(2,2) =1+15+8+4= 28\\
f(6,2) = 1+f(5,2) + f(4,2) + f(3,2) =1+28+15+8= 52
$$
You can even simplify this recurrence a bit more. The recurrence when $n$ is replaced with $n-1$ is
$$
a_{n-1} = 1+a_{n-2}+a_{n-3}+\dots+a_{n-k-2}\tag{$n>k+2$}
$$
Subtracting these equations
$$
\boxed{a_{n}=2a_{n-1}-a_{n-k-2}.}
$$
You can compute $a_n$ in $O(k^3\log n)$ time if you are careful. The last recurrence can be written as a matrix equation, which I illustrate when $k=2$:
$$
\begin{bmatrix}a_n \\ a_{n-1} \\ a_{n-2} \\a_{n-3}\end{bmatrix}=
\begin{bmatrix} 2 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 \\0 & 0 & 1 & 0 \end{bmatrix}
\begin{bmatrix} a_{n-1} \\ a_{n-2} \\a_{n-3}\\a_{n-4}\end{bmatrix}
$$
Letting $A$ be the $(k+2)\times (k+2)$ matrix, iterating the recurrence implies
$$
\begin{bmatrix}a_n \\ a_{n-1} \\ \vdots \\a_{n-k-1}\end{bmatrix}=A^{n-k-2}\begin{bmatrix}a_{k+2} \\ a_{k+1} \\ \vdots \\a_{1}\end{bmatrix}
$$
Therefore, you can compute the vector on the left by computing a power of the matrix $A$. Using exponentiation by squaring, this takes only $O(\log n)$ matrix multiplication, each of which naively takes $O(k^3)$ arithmetic operations.
Best Answer
I turns out that it’s easier to count the strings that don’t have a prefix divisible by $3$ and subtract the result from $2^n$. We just need to keep track of their remainder modulo $3$.
So let $a_n$ and $b_n$ be the number of binary strings of length $n$ without prefix divisible by $3$ and with remainder $1$ and $2$ modulo $3$, respectively.
If we append a $0$ to a string of length $n$, we get $a_n$ strings with remainder $2$ and $b_n$ strings with remainder $1$. If we append a $1$, we only get $b_n$ strings with remainder $2$ (because if we append a $1$ to a string with remainder $1$, it becomes divisible by $3$). Thus
\begin{eqnarray} a_{n+1}&=&b_n\;,\\ b_{n+1}&=&a_n+b_n\;.\\ \end{eqnarray}
Substituting the first equation into the second yields $b_{n+1}=b_{n-1}+b_n$, the recurrence for the Fibonacci numbers. The initial values are $b_1=0$, $b_2=1$, shifted by $1$ respect to the Fibonacci numbers, so $b_n=F_{n-1}$, and thus $a_n=F_{n-2}$. It follows that the number of binary strings of length $n$ with a prefix divisible by $3$ is $2^n-F_{n-1}-F_{n-2}=2^n-F_n$, so the probability for a uniformly random binary string of length $n$ to have a prefix divisible by $3$ is $1-2^{-n}F_n$.
For prefixes divisible by $4$, we can keep track of strings ending in $10$ and in $1$ and subtract them from $2^n$. If we denote their counts by $a_n$ and $b_n$, respectively, we get the same recurrence again as above, but with different initial values: $b_1=1$, $b_2=1$, so now we have $b_n=F_n$ and $a_n=F_{n-1}$, so the proportion of binary strings of length $n$ with a prefix divisible by $4$ is $1-2^{-n}F_{n+1}$.
If you look at the OEIS entry for the Fibonacci numbers, you’ll find that they count binary strings that fulfill various conditions, but having a prefix divisible by $3$ or $4$ isn’t mentioned there yet.
For modulo $5$, things get slightly more complicated. We need to keep track of all four remainders. Denoting the counts for remainders $1$, $2$, $3$ and $4$ by $a_n$, $b_n$, $c_n$ and $d_n$, respectively, we have
\begin{eqnarray} a_{n+1}&=&c_n\;,\\ b_{n+1}&=&a_n+c_n\;,\\ c_{n+1}&=&d_n+a_n\;,\\ d_{n+1}&=&b_n+d_n\;,\\ \end{eqnarray}
or in matrix form,
$$ \pmatrix{a_{n+1}\\b_{n+1}\\c_{n+1}\\d_{n+1}}=\pmatrix{ 0&0&1&0\\ 1&0&1&0\\ 1&0&0&1\\ 0&1&0&1\\ }\pmatrix{a_n\\b_n\\c_n\\d_n}\;. $$
Unfortunately this matrix has a rather messy eigensystem (I dare you to click “exact form” :-), so we can’t express the result in a nice closed form, but we do find that the largest eigenvalue (and the only one of magnitude greater than $1$) is approximately $1.75488$, so whereas the number of binary strings of length $n$ grows as $2^n$, the number of binary strings of length $n$ without prefix divisible by $5$ grows approximately as $1.75488^n$, compared to the golden section ratio $\left(\frac{1+\sqrt5}2\right)^n\approx1.61803^n$ for the Fibonacci numbers in the case of modulo $3$ or $4$.