Years ago the advice for a TM Drive was just "larger than the backup disk". Seems really weird that so much extra space is needed. Double the space should be more than enough.
Strictly speaking twice the total amount (of the aggregate amount of source volume data—not capacity—and calculating the former is not trivial) should be adequate, and the only reason it's not a good idea to partition a drive used for TM backups is that a catastrophic failure could render all its partitions simultaneously lost. Even then, if you designate a drive exclusively for TM's purposes, one and only one backup drive isn't enough anyway.
The most common reason for that message is drive failure. Run DFA on both the source volume and its TM backup. Whatever the problem is, it's not related to the capacity of the TM backup partition. Insufficient space would generate a different error message.
Now, do I have to buy a new HD in order to format my present HD to APFS?
No. As far as Time Machine is concerned just forget anything you may have read or heard about APFS. Questions like that make me wish Apple never said anything about APFS at all. From the user perspective Time Machine works the same way it always has.
For additional troubleshooting suggestions read below.
- Troubleshooting can be time-consuming but here are some steps that might help identify or correct common problems.
- Extracting Time Machine log activity may or may not yield useful data, but if you are interested those instructions follow below. It might be just the beginning of troubleshooting efforts that are likely to take some time. Otherwise, you can skip this section and go right to the "reconnect" procedure below it.
To extract potentially relevant Time Machine activity from log consider using the following shell script:
clear; printf '\e[3J' && log show --predicate 'subsystem == "com.apple.TimeMachine"' --info --last 24h | grep -F 'eMac' | grep -Fv 'etat' | awk -F']' '{print substr($0,1,19), $NF}'
Copy (triple-click to select the entire line) and Paste that line in a Terminal window. The Terminal app is in your Mac's Utilities folder.
It extracts Time Machine activity logged during the previous 24 hours. To change that time period change that value. If Time Machine is running there is no need to interrupt TM to use it. Be advised that log is fairly resource-intensive, and if you are using a portable Mac it will consume a lot of battery power as it runs.
log will need a few moments to extract the Time Machine log data. Wait for it to finish. It is normal for its results to include various "errors" and "failures" and none of them are necessarily an indication of anything wrong.
Copy (Edit > Select All and then Copy) and Paste that Terminal window's contents in a reply to this Discussion. Please omit or obscure any information that you may consider personal.
Quit the Terminal app when you're finished with it.
The following technique can be used to "reconnect" to the backup disk. It will not affect the existing backup history in any way.
Open Time Machine's Preferences and de-select the Back Up Automatically checkbox. Make sure no backups are in progress, otherwise you should wait for it to finish or terminate.
If the backup disk is directly connected to the Mac, disconnect it: drag its icon to the Trash, wait for it to disappear from the Desktop, and then physically disconnect it from the Mac.
If its icon does not appear on the Desktop, select External Disks in the Finder menu > Preferences... > General. You can de-select it later.
Then, click the "Select Disk..." button, select the backup disk, then Remove Disk, then Stop Using This Disk.
If you designated more than one backup destination, the "Select Disk..." button is replaced by an "Add or Remove Backup Disk..." option. You have to scroll through the list of backup disks for that option to become visible.
This will not affect any existing backups.
Reconnect the backup disk to the Mac, power it on if required, and wait for its icon to appear on the Desktop.
Then, Select Disk... again in Time Machine's Preferences. Re-select the same one under Available Disks, then Use Disk. If the backup is on a network (TC or AEBS), you will be prompted for the password you provided for that disk in AirPort Utility.
"Waiting to complete first backup" will appear, which means it won't do anything until the next scheduled backup. Despite the implication of that message, it does not mean it needs to create a completely new backup, as if it's creating a brand new one. Your existing backups will still be available.
If you don't want to wait that long, select Back Up Now.
A Notification may appear if your source volume is encrypted and the backup volume is not. That's normal.
Re-select Back Up Automatically. The "Preparing Backup..." status message will remain for a long time. Eventually, "Backing up xxx of yyy" will appear, but those values will not be accurate, nor will the "Estimated time remaining" in Time Machine's Preferences. Just ignore it. It may take a few hours even if your Mac is not allowed to sleep. Time Machine will also pause or become slow if you use your Mac for tasks it considers a higher priority.
For fundamental troubleshooting references please read If you can't back up or restore your Mac using Time Machine - Apple Support and Time Machine troubleshooting - Apple Support.