Try 999077; this is the internal code for Hong Kong once your package reaches mainland China.
Half of my HK customers do not use ZIP codes. I have been shipping there for many years. International shipping is a problem with HK because of the formatting issue.
Pitney Bowes is the one that rejects the shipping label. They should be in charge of eBay's addresses.
I used to go straight to PayPal and print problem labels there, the system is still PB bit it can be manipulated differently than eBay shipping.
Now that I am on MP I have to use PayPal Ship Now to get things done when eBay shipping says no go.
Malaysia is another one with format issues as well.