This is an intriguing problem! And it's ripe for a recursive approach. However, the details would seem to indicate that a general formula for the maximum probability of winning the game may not be so easy to find, and hence this answer is incomplete. For the cases considered below though, the strategies are indeed optimal.

Let $S_{n,k}(b)$ be the maximum probability of winning the game for the given inputs. Since at any stage there is only one choice to be made - namely how much of the budget $b$ to assign to $p$, the probability of obtaining a head - all possible strategies are parameterised by $0 \le p \le \text{min}(1,b)$, and we hence have the following recurrence relation: 
\begin{equation}\label{rec}
S_{n,k}(b) = \text{max}_{0 \le p \le \text{min}(1,b)} p \cdot S_{n-1,k-1}(b-p) + (1-p) \cdot S_{n-1,k}(b-p),
\end{equation}
since a head (occurring with probability $p$) decrements both $n$ and $k$, while a tail decrements $n$ only.

We define $S_{0,k}(b) = 0$ for $k \ge 1$ and $S_{n,0}(b) = 1$ for $n \ge 1$ and any $b$. Using~(\ref{rec}) and these base cases it is easy to obtain $S_{n,1}(b) = \text{min}(1,b)$ for $n \ge 1$. It is also easy to show that $S_{2,2}(b) = \text{min}(1,b^2/4)$, setting $p=b/2$ for each toss.

The first non-trivial case is 
$$
S_{3,2}(b) = \begin{cases} 
\frac{b^2}{3} - \frac{b^3}{27} & \text{if} \ 0 \le b \le 3/2 & (\text{set} \ p = b/3)\\
\frac{3b-2}{4} & \text{if} \ 3/2 \le b \le 2 & (\text{set} \ p = b-1)\\
1 & \text{if} \ b \ge 2,
\end{cases}
$$
which is obtained by substitution and differentiating w.r.t. $p$.

$S_{3,3}(b) = \text{min}(1,b^3/27)$, by setting $p = b/3$, while the next interesting case is
$$
S_{4,2}(b) = \begin{cases}
\frac{b^4}{256} - \frac{b^3}{16} + \frac{3b^2}{8}& \text{if} \ 0 \le b \le 4/3 & (\text{set} \ p = b/4)\\
\frac{19b-11}{27} & \text{if} \ 4/3 \le b \le 2 & (\text{set} \ p = b-1)\\
1 & \text{if} \ b \ge 2.
\end{cases}
$$

It should be possible to prove a (recursive) formula for $S_{n,2}(b)$ based on the above. However, for $k=3$, $n \ge 4$ this may be somewhat harder. In particular for $0 \le b \le 2$ we have $S_{4,3}(b) = b^3/15 - b^4/128$, setting $p = b/4$. 

For $2 \le b \le \alpha \approx 2.84$ we have $S_{4,3}(b) = r(b) \cdot \frac{3(b-r(b))-2}{4} + (1-r(b))\cdot\frac{(b-r(b))^3}{27}$, where $r(b)$ is the root in $[0,1]$ satisfying
$$
16r^3 - (36b+12)r^2 +(24b^2 +24b - 162)r -4b^3 -12b^2 + 81b -54 = 0,
$$
and $p = r(b)$. For $\alpha \le b \le 3$, setting $p = b-2$ is optimal and gives $S_{4,3}(b) = 19b/27 - 10/9$.

It would seem that for larger $k$ (and $n$) these computations become increasingly cumbersome (or interesting, depending on one's perspective).