And of course "Revenge is a dish best served cold" is absolutely not a "Klingon proverb." It's a real saying that's been around for centuries in multiple cultures, notably popularized in the French novel Les Liaisons Dangereuses
. Nicholas Meyer seemed to make a running gag of having characters attribute old Earth sayings or writings to alien cultures, like Spock claiming "Only Nixon could go to China" (a political aphorism coined in 1971) as a Vulcan proverb, and the bit about "Shakespeare in the original Klingon." Maybe sort of a variation on Chekov's "Russia invented everything" gimmick.
So yeah, Khan would've needed to learn about Klingons from the reading materials Kirk provided, but attributing that Earth proverb to the Klingons may have been a joke on Khan's part or maybe the result of his failing memory or derangement.