I really don't care that much about whether the card ist too strong or too weak - the major problem is, no one will really have fun using it. If you want this to happen it either has to
1.) be tricky how to play it
2.) be a game-changing decision whether you take it or not
3.) change the style of the game in an innovative way
Well, 1.) obviously doesn't hold, but that's not a crime ...
2.) is more problematic, because compared to e.g. market, which is boring at play as well, the decision to buy "market or outpost" changes your deck. Whereas "King or province" can be broken down to the decision "will I play this card twice or more often?". If yes, King is probably better, if not, Province is; but even if this decision is sometimes not an easy one, it won't really affect the nature of what you do. If the decision is close, that means we are in the endgame, and you can no longer decide to adapt your deck to the King you purchased.
3.) Now suppose you want that king, yeah. What does that mean? It might make you go engine, and it might even be the tiebreaker that makes you go for it from the beginning. But the engine you will build will probably look exactly the same as with other Payloads. It's hard for me to think "Oh, it will be a kings engine, there's an interesting specific way I have to build it".
tl;dr: At 8$, a card has to be gamechanging like Prince or Possession, otherwise, it's too boring.