O Cervo foi sempre coroado quando o sigilo foi tirado do da Casa Durrandon.
Durante Aegon's Conquer, Orys Baratheon, um dos generais de Aegon I foi encarregado de tomar Storm's End da House Durrandon. Depois de se casar com a filha de Lorde Argilac, ele tomou as palavras da Casa e sigilo para ser seu, como o sangue da linha Durrandon continuaria através dele.
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
Parece que Orys fez isso em respeito ao rei caído.
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
As seguintes informações devem a @Aegon por sua ajuda nos comentários.
A TWOIAF afirma que foi o Rei da Última Tempestade, Argilac, que acrescentou a coroa ao cervo.
Para responder a outra parte da sua pergunta:
Não, novos reis não adicionam coroas ao seu sigilo. Múltiplos exemplos existem de casas que se elevam à realeza e não mudam seu sigilo, sendo mais notáveis a Casa Lannister, a Casa do Jardineiro, a Casa Stark e a Casa Hoare.
Um exemplo de um rei adicionando uma coroa ao seu sigilo é Euron Crow's Eye, que depois de matar seu irmão Balon, se torna o Rei das Ilhas de Ferro e do Norte.“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
No entanto, devemos notar que este era apenas o sigilo pessoal do Euron, e não o da Casa Greyjoy.