Balls & Bins: A punishment and reward game
Here's an argument that it's polynomial for $k=2$. 

If $k=2$, each bin can only be connected to two other bins, and thus the graph falls into paths and cycles. We can thus just worry about a cycle. In fact, we can guess which bin is capped first. Since there are only a polynomial number of guesses, we can try all of them, and reduce the problem to the case where the graph is a path.

Now, whether a bin can be capped only depends on whether or not you've capped its neighbors. That is, for bin $1$, we have one of the following constraints:


bin $1$ can be capped only before you've capped bin $2$,
bin $1$ can be capped only after you've capped bin $2$,
bin $1$ can be capped any time,
bin $1$ can never be capped.


For case 1, you might as well cap bin $1$ as the first thing you do. Now, you have a path of length $n-1$, and you can use recursion. 

For case 2, you might as well cap bin $1$ as the last thing you do. Now, you have a path of length $n-1$, and you can use recursion.

For case 3, capping bin $1$ will either add or subtract balls from bin $2$. If it adds them, make it the first bin you cap. If it subtracts them, make it the last bin you cap. In either case, you've reduced the problem to a path of length $n-1$.

For case 4, you've solved the problem: it's impossible to win.

This gives an algorithm of time $O(n^2)$. For a cycle of length $n$, we need to test $n$ different paths, breaking the cycle in every possible place. And for a path of length $n'$, in constant time, we can convert the problem to the same problem on a path of length $n'-1$.