So yesterday I added the iCloud integration, and then overnight I get couple of these warnings. I was fast asleep and thousands of miles away from the ‘PDT’ timezone. Is this normal? I’ve changed my password and forced logout.
Now the integration isn’t working of course and there’s no apparent option to reconfigure it, but my biggest worry is if my account has been compromised. Should I worry?
Nothing to worry about would be too much, as cloud services always are more risky than a local space. 
BUT, with this mail, you don’t need to worry. It just tells you, that Apple noticed a different login, in your case not from the standard browser you normally use. And in your case that sounds right, as the HA integration is not a browser.
Just note, if there are any links in this mail, don’t use them, open your browser and type it in.
If you can’t set a new password in the intergration, delete the integration, don’t restart HA, just add the integration back again (with the new credentials) and after that you can safely restart HA.
Reassuring (a bit), but why would it say “PDT”, and why in the middle of the night? In my experience these notifications are sent immediately, not queued for delivery?
That should be the case. The first time HA checks with your iCloud, you will receive the notification. And PDT is PacificDayTime, sounds like Cupertino (CA) in the US. 
Integrations ask for data all the time, eg. HA asks every ten and a half minutes for a version check. Nothing unusual here.
And you already did what would be necessary, if something had gone wrong, you changed the password. Everything’s good to go, have fun with the iCloud integration.
