It is "ok" for the government to institute the death penalty, just as it is "ok" for the government to go to war -
- in the sense that a Christian should not violently oppose those things. However, in the realm in which a Christian has direct influence, those things should not be happening.
I don't think Paul would be much for protest. I think he would instead encourage acting in a way completely opposite to the way governments work, as a testimony to that alternative.