Ring of Mind Shielding (and a DM who cooperates)
Note: This depends on your DM accepting an interpretation of how a magic item works that is not explicitly clear.
If you are still being irritated by people spamming you with Sending, you may be able to justify the use of the Uncommon magic item: Ring of Mind Shielding.
The description for the Ring specifies...
Creatures can telepathically communicate with you only if you allow it.
And Sending's description says...
The creature hears the message in its mind
While it does not explicitly state that Sending is a telepathic communication, the plain language interpretation implies that it is. Thus, you could easily justify that a Ring of Mind Shielding is a ward against Sending. And 'If you allow it' could be interpreted that the King can maintain a 'Mental Whitelist' of people who are allowed to communicate with him telepathically.
Very few people can cast Sending
Unless you are in a very high magic world, Adventurers are rare. You can generally tell that they are rare because there tends to not be competition for all the quests you are doling out. And when big crises hit...the PC's party is almost always the only band of adventurers really doing something about that crisis. (Exceptions exist, of course). While no official statements have been released regarding demographics, we can look at a few settings for some ideas.
Faerun has not had any official material released on it, but makes it clear that Adventurers are Exceptional. Most of the numbers I have seen give a (generous, IMO) rating that maybe 1 in 100 people can become an adventurer. A full 1% of the population. If you then assume that about half of them reach the next level each time...the rest die or quit. Based on that: 0.0625% of the population will ever reach 5th level. So, in ten-thousand people--six have ever reached 5th level.
Eberron takes this even further. Characters with Adventurer levels are exceedingly rare. Small fractions of a percent of the population have even a single Adventuring level. And characters with 3-5 levels are famed war heroes. Admittedly, Eberron doubles down on the rarity of high-level characters.
Additionally, only three sorts of PC Class can cast Sending: Bards, Clerics, and Wizards. Even if you assume an even distribution (which you shouldn't) that means that 1/4 of Adventurers (3 of 12 classes) can use Sending.
So, out of your 6 in a ten-thousand characters, 1.5 of them can use Sending. On top of that, Bards can only use Sending if they specifically select that spell when leveling up.
So, we'll round down to 1 in ten-thousand as a (generous) nod to the fact that Clerics and Wizards are likely more rare than Fighters, Barbarians, and Rogues.
Note that this 1 in a thousand includes the Adventurers who are higher than 5th level as well, and whose concerns are thus even more removed from petty concerns like 'taxes.'
To again draw on The Realms for example...while the numbers given vary, the most common count is that there are about 130,000 people living in the city of Waterdeep. With an average distribution, that means there are about 13 people in the entire city who can cast Sending. If your King doesn't know the identity of those 13 individuals, he's not being very smart.
Now, granted, Waterdeep does NOT have an average distribution...the place attracts Adventurers like honey. But those Adventurers are there to adventure, so...
The people who can cast Sending probably have better things to do than annoy the King
Most likely, these are Clerics and Wizards. Assuming they are not out adventuring...Clerics are likely working at a temple--healing the sick, proselytizing, and otherwise serving their god. Wizards likely have their noses buried in their spellbooks, are training apprentices, or are working for some nobleman as their court mage.
A 5th level or higher Spellcaster is a powerful resource. They aren't likely to just be sitting on their hands, bored enough to irritate the King (and they may very well get preferential treatment from the nobility anyway--Makes sense to keep the person who can heal mortal wounds on your good side).
If you have a cooperative DM (or are the DM) a Ring of Mind Shielding can do the trick. But you probably don't need it.