It turned out that my initial theory was correct. By going into Central Administration -> System Settings -> Configure Managed Accounts and editing the SPFarm account, I could set the stored password to its correct value. Check "Change password now", "Use existing password" and enter the account password. This will update the stored password value, and the Timer service will start working.

No idea how the service got the wrong password in the first place, but this solves the issue.

It turned out that my initial theory was correct. By going into Central Administration -> Security -> Configure Managed Accounts and editing the SPFarm account, I could set the stored password to its correct value. Check "Change password now", "Use existing password" and enter the account password. This will update the stored password value, and the Timer service will start working.

No idea how the service got the wrong password in the first place, but this solves the issue.