Apple ID Two-Factor Authentication: Can't Approve This Mac
(Solution for macOS 10.13.6 High Sierra; YMMV with other OS versions.)

Hoo boy, it was a looong process, but I just got it working! First I'll share some general useful tips that might help, and then I'll attempt to walk through the exact steps I went through to resolve the problem. If you're struggling with this, too, then you can do it. I believe in you!

So, first, some useful things to try in general:


Restart your devices. This will force them to ask the Apple ID servers for re-authentication, and might clear up any erroneous cached data.
Turn it off and on again. No, seriously, turn off 2FA. This is your best bet at resetting things. Best in combination with the above. But how? Good question. The only way to turn it off nowadays is right after turning it on, from the email they send to every email address associated with your account when you turn it on. Click the link in the fourth paragraph entitled "return to your previous security settings":



From here it will ask you to reset your password, and you'll have to answer your security questions again next time you log in, but two-factor auth will be completely off—server-side, anyway, your devices might still be confused. See below.



Now, I'm going to go though the exact steps I followed to get out of this mess. Here, I'll refer to the Mac as, well, the Mac, and also a "Second Device"; this is the device that the Mac wants you to approve itself from. The Second Device can be an iPhone, an iPad, or any other Apple device that can receive 2FA verification codes. Here we go:


First, turn off 2FA as outlined above. This is required. If for some reason you can't access the email they sent you, I'm 99% sure you're out of luck and will have to reset encrypted data. Please link multiple email addresses to your Apple ID in the future.
This whole issue seems to be caused by the Second Device being completely off when the Mac attempts to enable 2FA. That said, restart both the Mac and Second Device and make sure you are signed into iCloud on both.
Go to System Prefs on your Mac again. It will probably still have the "approve your Mac" nag, or some other text saying that you have to "update your Apple ID details" or whatever. Just click the "Continue…" button next to that.
Since 2FA is now definitively off on your account (even if the text on that previous screen might have suggested otherwise), it will prompt you to enable 2FA as if it were the first time. Click through the dialogs, saying yes, you want to enable 2FA. Enter your phone number and follow the standard steps.
After this is complete, it may ask you to log in again on both your Mac and Second Device. Do so on both now. If the Mac prompts you for the login password, don't enter it yet, you'll do that in the next step. If the Second Device needs verification (not "approval") with a 2FA code, click Allow on the Mac and enter the code on the Second Device as usual. If it requires "approval", you need to turn off 2FA and start again (because at this point, both devices want approval from the other. Turning off 2FA will stop the Second Device from asking approval, breaking that loop of death).
Make sure the Second Device is logged into iCloud. Make triple-sure.
Now, crossing your fingers, eyes and toes, enter your login password into the prompt on the Mac.
If the stars are aligned and all is well with the world, your Second Device has just asked you to approve your Mac for use with your iCloud account. Enter your Apple ID password and say "Yes, I Approve" or whatever.
The Mac should receive the message that it's been approved from the Second Device and stop nagging you.
If you got here following step-by-step, then congratulations, you've just done it! Two-factor authentication is enabled on your account and both devices are approved and ready to go. If you have any other Apple stuff signed into iCloud then you'll have to verify those, too, but this'll just need the standard SMS-able 2FA codes. It's only the one device on which you set up 2FA that's special and requires this "approval" step. If you ask me, Apple really needs to get their act together here with this special one-time step that has no easy or obvious "out" option; I'm no security architecture expert by any means, but… sigh.


If you're still struggling, just know that this took me four attempts involving turning 2FA off and on again, and trying different patterns of restarting and re-enabling 2FA on different devices, to finally get this solved. So, I ask you to keep trying. You might just get it. Good luck. :)