One problem here is that only the winter fur of stoats living in colder climates produce the snow white fur so sought after. As a nice, fine warming winter gear is is expensive, but there are/were more expensive furs out there, for example sable.
As a symbol of purity for example it was already established as such by Zoroastrians. The first use by any form of nobility or royalty will therefore be hard to pinpoint.
The ermine, a relatively large weasel, was sacred to the Zoroas- trians. Because of its white color, it has often been associated with the fierce chastity of a soldier of God, and Mary Magdalene was depicted wearing an ermine coat to show that she had reformed. A popular Eu- ropean legend stated that an ermine, pursued by hunters, would al- low itself to be killed rather than soil its beautiful coat with mud.
Boria Sax: "The Mythical Zoo. An Encyclopedia of Animals in World Myth, Legend, & Literature", ABC-Clio: Santa Barbera, Denver, 2001.
This is part of fashion history and therefore closely linked to conspicuous consumption: you want what others cannot have. Sometimes this was byssos, sometimes ordinary silk, and it could be cotton, as long as it was in short supply.
But during the medieval period ever more people got rich enough to challenge ancient dress codes. While Charlesmagne enacted a law that prohibited too much extravaganza, by the 14th century dress codes were so often and widely violated that they had to be constantly adapted, updated and modernised.
This process took some time and did not spread uniformly across all of Europe, although it eventually reached the most back-waterish corners.
There is a certain cross over with heraldry:
Since the origin of armorial bearings in the middle of the twelfth century, the furs ermine and vair have been featured in heraldry. Heraldically, the furs are patterns of two or (occasionally) more colours, but are treated more or less like solid colours. Because they are treated like regular colours, they are classed among the heraldic tinctures. The furs are originally based on the real-life patterns of medieval fur clothing.
Ermine is the popular name of a weasel species (mustela erminea). The wintertime pelt of the ermine is white right down to the tip of the tail, which is black. Historical ermine fur clothing would generally be white, with the black tails scattered around the surface. The complexity of ermine lay in the tails, because the shapes of ermine tails are by no means standardized in artistic representation. There are many variations on ermine spots recorded in art, some resembling the thin black point of a tail, others more fanciful and stylized. Ermine clothing is common in medieval and Renaissance art, especially in the lining of cloaks, hoods and other garments. It remains in active use today, most notably in the official robes of UK peers whose scarlet robes include an ermine mantle denoting rank.
Ermine as it appears in heraldic art is very similar to ermine in medieval art. Many of the same variations on the ermine spot were used in the past, but heraldic art has gradually settled on one basic stylized design, with only minor variations. Because all the variations are at least loosely based on the use of ermine in clothing, the design has remained recognizable in all its iterations.
Daniel Phoenix: "‘Garments So Chequered’: The Bible Of Ciˆteaux, The Bayeux Tapestry And The Vair Pattern", The Antiquaries Journal, 90, 2010, pp 195–210.
It is assumed that the tincture ermine was first used in the coat of arms of Brittany but only became firmly entrenched as a symbol of royal power in France during the reign of Louis XIV.
But for England one of the first sumptuary laws that regulated the royal conspiciuous consumption came with Edward III (13 November 1312 – 21 June 1377):
The Royal Mantle
A large cloak or mantle, trimmed with fur, was an emblem of royalty and noble status. One of the most highly rated furs was ermine, made from the fur of the stoat.The coat of this little animal turns white in winter, except for the black tip of its tail.The white fur with spots of black was much admired, and from the reign of King Edward III (1327–1377) onward, only the royal family was allowed to wear it in England. Scarlet cloth trimmed in ermine was later adopted by European dukes as part of their ceremonial dress.
Philip Steele: "A History of Fashion and Costume. Volume 2. The Medieval World", Facts on File: Hove, 2005.
Going through Wikipedia pictures from Richard II backwards, this seems to check out.