For the matching lower bound, observe that no two kings can be adjacent, and if there is at least one king, the set $E'$ of ordered pair edges $(v,w)$ in $E$ with $v \in \mathrm{King}(G)$ and $w \not \in \mathrm{King}(G)$ is non-empty.  Now we do weighted double counting:
\begin{align*}
\# \mathrm{King}(G) &= \sum_{(v,w) \in E'} \frac{1}{d(v)}\\
&< \sum_{(v,w) \in E'} \frac{1}{d(w)} \\
&\leq \sum_{w \in V \backslash \mathrm{King(G)}} 1 \\
&= \#V - \# \mathrm{King(G)}
\end{align*}
hence
$$ \# \mathrm{King(G)} < \frac{1}{2} \# V.$$
Of course the same claim holds when there are no kings as long as the graph is not the empty graph.  So this shows that the lower bound provided by the complete bipartite graph examples are completely optimal.

This bound can also be viewed as quantifying a variant of the "[friendship paradox][1]".  (Based on this connection, I propose "influencer" as a more modern and gender-neutral terminology alternative to "king".)


  [1]: https://en.wikipedia.org/wiki/Friendship_paradox