So, when the Mac successfully logs into the Apple account for the first time, Apple sends a notification to the other devices that are currently connected to the same Apple ID (similarly to how it sends them the 2FA codes for the new login), and one of them contacts the new device and shares the encryption key with it. Is this the idea?
What if you only have one device attached to your iCloud account, and you're replacing it? Say, you're trading in your old phone for a new one, and you have no Macs or iPads. An obvious workaround would be to add your new phone to your account before removing the old one, but that may not always be an option.