Cannot finish first backup with Time Machine

Solution 1:

Anecdotally, after having seen similar several times, two things to try; one free, the other paid.

First clear down any stray local backups, from Terminal.

tmutil listlocalsnapshots / will list them.
tmutil thinlocalsnapshots / 1000000000000 1 will pretty aggressively cull them.

List again afterwards & make sure only one or two remain, & that none of them are tagged dataless.

Try running Time Machine again.

If still no joy, then the only way I've ever found to fix this is to run DiskWarrior on the Time Machine drive. Apple's Disk Utility never seems to work.
Fortunately, TM drives must be HFS+, as Disk Warrior cannot yet handle APFS.