But at first I will make up my mind about how to backup the databases both on an external harddrive and a cloud service…
We strongly advocate proper primary backups using TimeMachine (or similar snapshot-style backup applications) and external drives. Also, you should read the series of articles we posted: DEVONtechnologies | Search & Find
PS: it‘s just a Little frustrating, all the data is still in iCloud…
Yes, but it’s securely locked by the encryption key.
Depending on how the Mac was erased, and how much data has been written to the drive since that point, there is a tiny chance that recovery software like Disk Drill could recover the original database from the Mac https://www.cleverfiles.com