How to know when decryption fails in Yao's Garbled Circuits
Your intuition is correct, the encryption is set up to indicate a failed decryption when an incorrect key is used with the ciphertext. A very simple way of doing so can be as follow: when encrypting the message $m$ with the key $K$, encrypt $m||0^{\lambda}$ ($\lambda$ is a security parameter, e.g. 80 or 128). When decrypting a ciphertext, check whether the last $\lambda$ bits are $0$; if this is not the case, decryption failed.

Note that the paper you are reading describes also the point and permute technique, which allows to find out which ciphertext we should decrypt, without having to try them all. This is an important optimization for garbled circuits.