Time for an answer to the bonus question! We'll go straight to the generalized case. The theorem we shall prove is:
When $N, k$ are odd, the first player wins if and only if $n \leq k+1$ or $N \leq 2k + 1$.
We have chosen to assume that $N$ is odd, since if $N$ is even, it introduces the complication of draws. Moreover, without loss of generality we have assumed $k$ is odd; we may do this because the case $(N,n,k)$ with even $k$ is equivalent to the case $(N,n,k-1)$, since the ending difference between the two players' stone counts must also be odd whenever their sum $N$ is odd.
Now, we show the cases where the first player can win:
If $n \leq k+1$ we use the copying strategy in Rand al Thor's answer, i.e. take $n$ to start, and then copy player two afterward. Our lead is always between $0$ and $k+1$, and will not end in a draw with an ending difference of $0$ or immodestly with an ending difference of $k+1$ (the ending difference must be odd), so we are guaranteed victory.
So suppose $k + 1 < n$ and the second inequality $N \leq 2k + 1$ holds. Then we may take $k+1$ stones with our first move, which is already more than half in the entire game. We can keep our lead at the end of our turns at a maximum of $k+1$ using the copying strategy; again, the game finishes with our lead at most $k$ and so we win.
Now for the cases where the second player wins:
We have $k+1 < n$ and $2k+3 \leq N$. We write $N = 2k+3 + 2\ell$ for some $\ell \geq 0$, choosing to think of $N$ as composed of an "ending pot" of $2k+3$ stones plus two "lobes" of $\ell$ stones, one lobe for each player. Refer to these lobes as $L_1$ and $L_2$.
Our strategy as the second player: If $L_1$ and $L_2$ are empty because $N = 2k+3$, skip this paragraph. Otherwise copy the first player's moves (where we visualize him as taking stones from $L_1$, and us from $L_2$) up until he exhausts $L_1$, and possibly started digging into the ending pot. Once this happens, exhaust $L_2$ with our move and take no more.
Now, if the first player leaves the ending pot with $k+1$ or less in their next move, they lose since their lead would be at least $k+2$, and we can render them immodest by always taking a single stone. Otherwise, we take exactly $k+2$ ($\leq n$) from the ending pot, giving us a lead at most $k+1$ after our turn; as before, we are guaranteed to finish with more stones (all of $L_2$ and more than half of the ending pot) and a lead not exceeding $k$ after the final move.
Thus, for the case $N = 101$, $n = 5$ and $k = 3$ the winner is
the second player.