I can't think of a possible scenario where one would tell another to cool his heels (the very first time). Even if you walk a lot, only your legs hurt a lot. Why particularly heels?
How did it come into existence?
The idea seems to be that your feet become hot with walking and that when you stop walking they, and in particular, your heels, cool down. Hence, the current meaning of having to wait. The earliest recorded use of cooling the feet in this way is dated 1576. Coole their heeles first appears in 1606, where it appears to refer to horses. It is first applied to people in Chapman’s translation of the Iliad published a few years later.
In my youth in 1970s England, the expression was meant to denote being sent to wait in a corridor/ to see the Headmistress after some bad behaviour in the classroom. As in "she was sent to cool her heels in the corridor by the teacher". It implied awaiting some chastisement, and was used in English School Stories from the early part of the 20th Century.e.g. The Chalet School series.