Out of the Box i5 4690k at 80c with Hyper 212 Evo

Use Prime 95 version 26.6 with Small FTT test for thermal testing. Don't use a version any higher than 26.6
If you want to stress test, Realbench is one option as well as AIDA64.

Those temps are pretty high for stock speeds of the 4690k. As Suztera mentioned, the p95 version matters. The most recent version places an unrealistic load on the cpu. Version 26.6 and small fft's for a steady load is the one you should use for haswell/devil's canyon. When installing the 212 evo it has 4 screws to tighten it in place to the bracket. It also has a center thumb screw to increase pressure against the cpu, did you tighten that one as well?

Ambient temps will have an effect on cpu temperatures, what are your current pc room temps like? Thermal paste should be about the size of a grain of rice or so, too much can act as insulation between the cpu and cooler. It only needs to spread out to form a thin film to fill any tiny gaps between the cooler base and cpu. Try using realtemp to see if the temps are the same as hwmonitor.
http://www.techpowerup.com/realtemp/

That's really high temps for gaming. It might be worth removing the cooler, cleaning off the cooler base and cpu lid with rubbing alcohol (isopropyl) and snugging up that center screw/nut to make sure it's getting good contact with a fresh application of thermal paste. Auto overclocking tends to be a bit aggressive applying more vcore than necessary to make sure it's stable. That will cause higher heat. I would disable any overclocking through ai suite or 'performance' modes in the bios and get the temps under control at stock first. Then if you want to overclock try doing it manually through the bios.

That way you have a bit better control and will likely get whatever overclock it is (say 4.2 or 4.3) at a lower vcore than auto software will. It will help reduce your temps that way. Just a matter of stress testing and thermal testing after altering settings in the bios to make sure it's stable. I usually use prime95 v26.6 small ffts for thermal along with rog real bench and ibt for stability while monitoring with either hwinfo64 or realtemp.

Typically gaming should be around 60c or so (depending on ambient temps). Prime95 v26.6 should report higher temps than typical gaming. If I get 72c on p95, during games I usually get around 62-65c. My results will vary from yours, using a different overclock and larger air cooler but it's more or less a general point of reference for synthetic thermal test results vs real world temps.

Edit: here's a look at some different application methods for the thermal paste. Not to say you should use the 'x' shape over others, or to debate application methods but rather to show an example of a 'rice sized' bit of thermal paste for reference. It may help you determine if you're using too much paste or not.
https://www.pugetsystems.com/labs/articles/Thermal-Paste-Application-Techniques-170/

It's always possible, though highly unlikely. Any product made by any company can be faulty though there are a lot of settings involved in the bios, some of them may be 'automatic' or selected as 'optimal' or 'performance' mode settings which are actually slightly overclocked settings. It should turbo to 3.9ghz on its own when one core is maxed out, when two are maxed it will drop to 3.8 and when 3-4 cores are maxed it will drop to 3.7ghz. That's standard behavior for intel's turbo boost technology built into the cpu. An overclock would be locking all 4 cores to 3.9ghz or higher or allowing them to run higher with a raised multiplier and vcore voltage whether you did it manually or clicked a performance mode that did it for you.

A lot of cpu heat problems are attributed either to a mild overclock someone was unaware happened (such as 'turbo' or 'performance' mode in the bios) or cpu cooler installation not being quite right. That applies to both intel and amd both. Another thing that can cause higher than normal temps on a haswell or devil's canyon cpu is using a current version of prime95.

This intel temperature guide is a sticky at the top of the forum/cpu category. It looks like a more lengthy read than it is, has a lot of good info discussing the reason for using the older version of prime95 as well as other useful information about 'normal' or typical temps under various conditions.
http://www.tomshardware.com/forum/id-1800828/intel-temperature-guide.html

Honestly I'd bet there's either a less than optimal setting in the bios or through ai suite, use of a new version of prime95 or the cpu cooler just didn't mount quite flat. Try cleaning and reapplying the thermal paste, tighten that thumb screw in the middle of the cooler to increase pressure to the cpu heat spreader (metal cover of the cpu) and when tightening the cooler screws at the 4 corners be sure to tighten them just a little at a time in an "X" pattern. Ie, top left, bottom right, top right, bottom left - and work your way around until they're tight. It will help make sure it's tightened evenly to the cpu. Tightening one screw all the way down then another can result in the cooler feeling tight but being tilted a bit and not making good contact.

I can't recall off the top of my head, but just to be safe make sure there's no thin plastic film covering the base of the cooler. I don't recall the 212 evo having one, my other air cooler did have one. Sometimes companies place a thin plastic film to protect the base of the cooler in shipping/packaging. Not trying to insult your intelligence but sometimes people can miss it if there is one and it's one of those facepalm moments. That will have a serious impact on cooling performance if left on (if there is one).