No, it's not getting 'too hot'. No where in the field of electronics is 'too hot' defined as 'too hot to touch.'
Electronics get hot. This is a fact of life. Data sheets generally don't tell you if a certain component will get hot because you're supposed to know what things will get hot, how hot they'll get, and why. Power electronics is as much thermals as it is electronics.
And there is definitely no unwritten assumption that parts will always be cool enough to touch without burning you. In fact, this is rarely the case. That 1N5404 diode? It's maximum operating temperature is 150° C. If it isn't exceeding that temperature, then it isn't getting 'too hot'. There is nothing wrong with it operating continuously at 140°C for a long time, and in many real devices, diodes can and will operate that hot. Usually only when the ambient temperature as at the highest the product is rated, but still, it happens.
If you open up any old electronics with a bridge rectifier, often you'll see discoloration of the PCB in the area around these diodes. This is because those suckers get hot. And its ok. They're designed to operate in those conditions.
There are many MOSFETs that are rated to 175°C. The new Silicon Carbide based semiconductors have a theoretical operating range of 400°C (!!), though most are limited to 200-225°C due to their packaging epoxy not able to withstand any higher.
Anyway, yes, diodes get hot. Especially when you ask one with a 1.2V voltage drop to carry 1A, like in your case. Frankly, the 1N5404 is a wildly inappropriate diode for this application. So is the 1N4004, I am not sure what Maxim was thinking. But in your case, that diode is dissipating 1.2W at least. If it is getting hot, good. That means the circuit is working. If you don't want it to get hotter than you can touch, too bad, it's going to get too hot for you to touch.
Now, if you chose a diode with a lower voltage drop, pretty much any Schottky diode, it will get a little less hot. These diodes typically have about half the voltage drop of a silicon diode, so let's call it 600mV. This will cut the heat produced in half, to 600mW. It's still going to heat up though, but not quiet as much.
To put things into perspective, imagine the size of a 1/4W through hole resistor. Try putting 1/4th of a watt through it. It will get hot enough to burn you, but it will also tolerate this temperature perfectly fine, certainly much better than your finger will. That diode is shedding 5 times that. 1.2W might not sound like much, but tiny things get hot without many joules getting added to them.
As for the transistor, of course it gets hot, even with a heatsink. That's the entire point of heatsinks. To get hot. They work better if they're hot. They convect more heat via passive airflow, and if they're black, they'll radiate some heat too. Heat is even in the name. The transistor and heatsink are always going to be hot. All that matters is that they don't get too hot. You can lower the temperature it and the heatsink will eventually reach by either
Reducing the amount of power it must shed. So, make it waste less than 9W as heat. I don't think you can though with this circuit, as it's linear, and linear regulation works by burning off the excess voltage as heat.
Put a larger heatsink on it (this will still warm up, but it will not reach quite as high of an equilibrium temperature).
Make the room/ambient temperature cooler.
To put it bluntly, there is nothing that is wrong with your circuit, so much as something wrong with your expectations. Sorry. Heaters gonna heat.
