The Stag was always crowned as the sigil was taken from that of House Durrandon.
During Aegon's Conquer, Orys Baratheon, one of Aegon I's generals was tasked with taking over Storm's End from House Durrandon. After marrying Lord Argilac's daughter, he took the House words and sigil to be his own, as the blood of the Durrandon line would continue through him.
House Baratheon was born amidst the rain and mud of the battle known to history as the Last Storm, when Orys Baratheon thrice turned back the charge of the knights of Storm’s End and slew their king Argilac the Arrogant in single combat. Storm’s End, long thought to be impregnable, yielded to Orys without a battle (wisely, given the fate of Harrenhal). Afterward Orys took King Argilac’s daughter to wife and adopted the Durrandon arms and words as his own to honor Argilac’s valor.
The World of Ice and Fire - The Seven Kingdoms, House Baratheon
It seems Orys did so out of respect to the fallen King.
And afterward, to honor the fallen king, he took the arms and words of the Durrandon for his own. The crowned stag became his sigil, Storm’s End became his seat, and Lady Argella his wife.
The World of Ice and Fire - The Reign of Dragons, The Conquest
The following tidbits owe thanks to @Aegon for his help in the comments.
TWOIAF states that it was the Last Storm King, Argilac, that added the crown to the stag.
It was Durran Godsgrief the founder of House Durrandon who made the sigil and "crowned the stag".
To answer the other part of your question:
No, new kings do not add crowns to their sigil. Multiple examples exist of Houses rising to royalty and not changing their sigil, most notably being House Lannister, House Gardener, House Stark and House Hoare.
One example of a king adding a crown to his sigil is Euron Crow's Eye, who after killing his brother Balon, becomes the King of the Iron Islands and the North.
“The charge was one Sam had never seen before: a red eye with a black pupil, beneath a black iron crown supported by two crows. “Whose banner is that?” Sam asked. Xhondo only shrugged.”
A Feat for Crows - Chapter 45, Samwell V
However, we must note that this was merely Euron's personal sigil, and not that of House Greyjoy.