Can't start Time Machine backups on Catalina
As @Tetsujin suggested, the problem was indeed lack of space on the startup drive that I was trying to back up.

With 30Gb free, Time Machine was able to initiate a backup and stopped returning errors. (That is not likely the minimum limit; I just found something large and deleted it.)