Partial answer.
The game state should include the previous move. However, the restriction that the previous move can't be played is only meaningful if it prevents a good (winning) move, and the successor state doesn't remember the previous restriction. So, it will be fruitful to consider good moves ignoring the previous restriction.
If there are no good moves, then the restriction never matters; it is not blocking a good move. If there are multiple good moves, then the restriction never matters; it can't block all the good moves. If there is only one good move, the restriction might block it.
There are some numbers of stones that are P-states regardless of the previous move; these correspond with starting states where the second player wins (as the first move has no restriction). I will call these P$_0$-states.
I will denote a state as $(+q)$ if the next-smallest P$_0$-state has $q$ fewer stones. For $1 \leq q \leq k$, removing $q$ stones is a good move since it leads directly to a P$_0$-state. This means P$_0$-states are at least $k+1$ apart. Removing a different number of stones might also be a good move, but if the move leads to a $(+r)$ state with $1 \leq r \leq m$, then $r$ is a good move in that state, so our first move was only good if blocked this by also removing $r$ stones. Depending on $q$, we may be able to do this by removing more than $q$ stones (overshooting) or fewer than $q$ stones (undershooting). For undershooting, this means the only possible good undershot takes $(+q)$ to $(+q/2)$ (also meaning that undershooting can only be good if $q$ is even). For overshooting, we know we can only skip over one P$_0$-state at a time, so if the difference between the previous two P$_0$-states is $d$, then the only possible good overshot takes $(+q)$ to $(+(d+q)/2)$ (also meaning that overshooting can only be good if $d+q$ is even).
We also need to consider the case of $q > k$. It is impossible to overshoot here. For $q = k+1$, the only possible good move is $q / 2$. Sometimes this is a good move. For $q = k+2$, $q / 2$ is not possible since $q$ is odd, but we must consider $1$; but this also doesn't work (assuming $k>1$) because the $1$ doesn't block the good move $(k+1)/2 > 1$ from that successor.
Thus, P$_0$-states are either $k+1$ or $k+2$ apart.
For two consecutive P$_0$-states, intermediate states have either one good move or multiple good moves. Given this information for each intermediate state, we can characterize what happens up to the next P$_0$-state. If there is one good move, we know what it is. For $(+q)$, if $1 \leq q \leq k$, the good move is $q$. For $(q+1)$ (if it isn't the P$_0$-state), the good move is $(q+1)/2$. Then in the next interval, if we again want to count good moves, we have these automatic good moves, plus overshooting which only depends on our characterization of the previous interval (and depending on parity, there is only one or zero successors where the move will block the automatic good move), and undershooting only depends on the interval itself (no additional dependency).
Because this characterization (having fixed $k$) has only finitely many possibilities, eventually, things must repeat. (However, they don't have to repeat from the beginning. For example, with $k=55$ it seems that even the P$_0$-state spacing doesn't repeat from the beginning.)
It is fairly simple to characterize the interval between $0$ and the next P$_0$-state. We can only undershoot, and the only possible good undershot is halving. So, even numbers have two good moves if their half has only one good move. In other words, if we double a number, we alternate between having one good move or two good moves. Thus, whether $k+1$ is a P$_0$-state depends on the parity of the power of two in its prime factorization.
If $k$ is one less than a power of $4$, things work out quite nicely. This is the parity where $k+1$ is a P$_0$-state. But, by the great symmetry in way the powers of two work out (A007814), overshooting and undershooting in each block work out the same. Overshooting is only possible for even numbers, and takes them from $(+q)$ to $(+(k+1+q)/2)=(+(k+1)/2+q/2)$. The symmetry in the powers of two means this has the same power of two as $(+q/2)$ meaning the whole pattern repeats perfectly.
If the power of two in $k+1$ is $2$, then we know $k+1$ is a P$_0$-state. Whenever the previous interval between P$_0$-states is $k+1$, overshooting can only be a good move for $(+q)$ when $q$ is even. By induction we can show all P$_0$ intervals are $k+1$. $(k+1)/4$ is odd, so it doesn't benefit from overshooting or undershooting and thus a $(+(k+1)/4)$ state has only one good move. Thus a $(+(k+1)/2)$ state can be undershot so it has at least two good moves (we don't know about overshooting). Thus we can't have a $(+k+1)$ state as it can't block the two (or more) good moves in $(+(k+1)/2)$.
If the power of two in $k+1$ is a larger even number, we can make a similar argument, but we need to be more careful. We need to consider overshooting for $(+(k+1)/2^i)$ when $i\geq 2$ is even and show it isn't an additional good move. Overshooting takes this to $(+(k+1)/2+(k+1)/2^{i+1})$. So, it is clear that we should consider all states of the form $(+\sum_j (k+1)/2^j )$ (where $2^j>1$ divides $k+1$) as this set of states is closed under overshooting and undershooting. Overshooting or undershooting increases the largest $j$ by $1$ until terminating in a state $(+q)$ with odd $q$ which can't be overshot or undershot, so we can argue essentially the same as before (with a stronger inductive hypothesis).
The general case seems like it can be complicated.
