Since you know the solution when k=0, just alter it slightly...

Given the strategy of the prisoners, understand there is a point when the count will no longer increase for the counter. With k=0 and the sol'n you know, this point is exactly n-1. When k is non-zero there is a lower/upper limit to this count depending on if the king works to increase/decrease/not effect the count. Call the limits on this range [A,B]

So what do we do...well...
For any other k, let the prisoners effect the chalice Y times (for k=0, Y=1), where Y makes the following true:

The lowest possible total count (A) when all n-people have been in the room is greater than the maximum possible total count (B) when fewer than n-people have been in the room.

From here you have some algebra to determine Y. Plus you have a point where the counter can be sure everyone has been in the room.

I hope I worded this correctly...but, yes it is still possible.