Here's a simple algorithm:
We repeatedly pick a stack with a red element and execute a subroutine (to be described below) that tries to pop the topmost red element out of the stack. Either we will end up popping every red element or at some point every stack with a red element will have the subroutine failing. In the former case, it is clearly possible to pop all the red elements. In the later case, every topmost red element can't be popped, so in fact no more red elements can be popped, and so popping all the red elements is impossible.
Simply pop elements out of the stack in question (pushing blue elements into other stacks) until either a red element is popped (success) or until the blue elements being popped cannot fit into the other stacks (failure).
The subroutine requires at most $n$ operations, and the subroutine must be executed at most $k$ times in order to either conclude that a solution is impossible or to pop one red element. Since there are at most $n$ red elements. The overall runtime is $O(kn^2)$, which is polynomial in $n$ and $k$.
Certainly if this procedure pops all the red elements then popping all the red elements is possible.
Now suppose the subroutine fails on a stack. Define the "blocking" elements in a stack to be all blue elements above the topmost red element. Subroutine failure can only happen if all the blocking elements in the stack and all the elements in all other stacks cannot fit in the other stacks. Thus, this topmost red element cannot be removed until the count of blocking elements plus elements in other stacks decreases. In other words, the topmost red element cannot be the next red element popped.
If the subroutine fails for every stack with a red element, then no red element can be the next red element popped. In other words, no remaining red element can be popped at all.
Since every operation is either reversible (moving a blue element between stacks) or purely beneficial (popping a red element), reaching a state where the subroutine fails for every stack implies that all along the problem could not be solved.