Somewhat by accident, I discovered a way to recover the macros. This works for iCloud, not sure about other service providers.
- Navigate to your iCloud .kmsync file location
- Double click it. This should open a pop up window notifying you about a sync conflict, prompting you for a resolution
- Tick checkboxes for the last few snapshots (in my case, I narrowed it to 2, several hours apart).
- Save these files
- Go to Keyboard Maestro's General Preferences, uncheck and check again Sync Macros
- Load the file of choice (if you're not sure which one, make an educated guess based on the edit time and file size – you can always repeat steps 5–6 with another file)
In my case, I was fortunate enough to recover a dozen of my macros that I've created yesterday.
Just to let you know, for some reason double clicking any of the recovered .kmsync files directly won't load them to Keyboard Maestro, it has to be done via the Sync Macros checkbox route.