Today I received the message below, after booting my PC:
What exactly is an "Evil Maid"-attack? What are possible ways to get attacked by this? What does it mean in this case, that my disk "may have been tampered"?
"Evil maid" attacks can be anything that is done to a machine via physical access while it is turned off, even though it's encrypted. The name comes from the idea that an attacker could infiltrate or pay off the cleaning staff wherever you're staying to compromise your laptop while you're out.
For an encrypted device, the most likely evil maid attacks are some form of keylogger, either physical or software. Physical loggers are all-but-impossible to detect in software but can be found by physical examination (although depending on the available space inside a laptop and how easy it is to disconnect the keyboard, it could possibly be done in a way you wouldn't see without disassembling it again yourself...). Software keyloggers are a major threat, though.
The VeraCrypt bootloader (which takes your password and decrypts the encrypted volume or at least the next required part for booting) must itself be decrypted - if it were encrypted, it couldn't execute without something else to decrypt it - so it's a prime target for a place to put a software keylogger. Take an encrypted hard disk, attach it to another machine, replace the VeraCrypt bootloader with a compromised one that secretly saves the password, and put it back in the victim's machine. Next time the victim boots the computer, their hard disk password is logged for later retrieval. VeraCrypt attempts to detect this by computing a cryptographic fingerprint of the bootloader to see if it's been tampered with, although a skilled attacker could thwart this as well unless the machine is using a TPM or similar that checks the bootloader against a key which the attacker can't overwrite.
So, it looks like that verification of the bootloader failed. That's why VeraCrypt is telling you to change you hard disk password immediately. The attacker probably can't steal the password as you enter it - it would be a multi-stage attack instead, first compromising the bootloader and then retrieving the password later after you've had a chance to enter it - but if they get to the machine again after you unlock it once but before you change the password then they could steal that password (and all data on the disk).
Of course, it's possible that something totally innocuous happened and there is no attacker. Anything that messes with hard disks at a low level, like partitioning tools, backup/restore tools, OS installers/updaters, or a few other things could potentially invalidate the bootloader fingerprint without actually doing anything malicious. Changing the password is still probably a good idea anyway, though... when was the last time you did that?