Why is the Caching service stuck waiting for push token and never starts on OS X Server (Mavericks)?
The clue came from the system log, looking at the entries from Apple Push Services Daemon (apsd):

apsd[69]: Hardware SerialNumber "System Serial#" looks incorrect or invalid


It turns out that this machine had a logic board (motherboard) replaced a while ago by Apple, and they never bothered to flash the machine's serial number. The only fix is to look for the tool that Apple technicians themselves use to flash the serial number onto a new motherboard.

I had to write down the serial # from the bottom of the stand and double-check on apple's support status site to make sure it matches my system. The serial flash tool will only let you set a new number, it won't change it, so if you mess up you're out of luck.

After running the tool and rebooting the system, the caching service started correctly without further ado.