(i'm just trying to find what am I missing...)
Assuming John have a clear text message , he can create a regular
hash ( like md5 , or sha256) and then encrypt the message.
John can now send Paul the message + its (clear text)hash and Paul can know if the message was altered. ( decrypt and then compare hashes).
Even if an attacker can change the encrpyted data ( without decrypt) - - when paul will open the message - and recalc the hash - it wont generate the same hash as the one john sent him.
so why do we need hash by key ?