Solution
If you recently attempted to sign into iMessage, wait at least 30 minutes without attempting to sign in.
Open System Preferences → iCloud. If already signed in, sign out.
In System Preferences, enter your Apple ID and password, and click "Sign In".
Wait until you receive an Apple ID Verification Code on one of your other devices. Do not use this code in System Preferences!
In the Messages app, sign into iMessage with (1) your Apple ID and (2) your password followed by the verification code you received. For example, if your password was "correcthorsebatterystaple" and your verification code was "123456", you'd enter "correcthorsebatterystaple123456" in the password field in Messages.
Messages should sign in successfully! If you do not use iCloud for anything else on your Mac, you can stop here. Otherwise:
Go back to System Preferences. Attempt to sign into iCloud with your Apple ID and password (no verification code).
Wait until you receive a new Apple ID verification code on one of your other devices.
In System Preferences, sign in with your Apple ID and your password followed by the most recent verification code.
Explanation
I don't know what changed on Apple's servers, but for some reason, Macs running OS X 10.9 are limited to one iMessage sign-in attempt per approximately 30 minutes.
This conflicts with Apple's standard login process for older devices. Normally, the process looks like this:
- Enter your Apple ID and password.
- Receive a verification code.
- Re-enter your Apple ID and your password followed by the verification code.
This is a really clever system! It allows older Apple software (from before the introduction of two-step verification) to continue signing in to modern accounts, without any client-side updates. However, it requires users to attempt to sign in twice in a row, and Messages can only attempt to sign in once every 30 minutes. This is longer than the time it takes verification codes to expire.
Luckily, System Preferences is not limited to one sign-in attempt per 30 minutes, and Apple doesn't seem to mind that we're using the code in a different app from where we requested it.
This answer is valid as of August 10, 2024 and I do not know what Apple's servers will decide to allow in the future.