Is the probability of at least $k$ consecutive heads higher for a coin with higher probability of heads?

A simple proof uses the beautiful idea of coupling. Roughly speaking, one realizes the results of the $p$ coins and of the $q$ coins on the same probability space, using the same randomness.

More precisely, consider $N$ i.i.d. random variables $U_k$, uniform on $(0,1)$, and decide that the result of flip $k$ is heads if and only if $U_k\leqslant p$. Then, replacing $p$ by $q\gt p$ increases the number of heads, pointwise, hence $P_{k,p}\leqslant P_{k,q}$.

Finally, the inequality is strict since, when $p\lt U_k\lt q$ for every $k$, the $q$ event is realized while the $p$ is not, and this has positive probability. (The argument shows that $P_{k,q}\geqslant P_{k,p}+(q-p)^N$.)