This is a difficult question to answer. First a minor point of clarification: the term "troll" can mean many things depending on the location in Scandinavia. I think it is safe to assume that you are referring to the array of supernatural beings that figure in popular fantasy literature and films and that the trolls you are asking about are the big ogre-like monsters.

One of the reasons why this is a difficult question to handle is that cultures nearly universally emerge from prehistory with beliefs and stories dealing with a full array of supernatural beings. Finding a point or origin in a prehistoric past is nearly impossible and can only be a matter of speculation.

The focus of what is certainly the subject of your enquiry is the pre-industrial inheritance of Northern Europe. Medieval Norse literature frequently mentions these sorts of supernatural beings. It is not clear if these entities are identical to what nineteenth-century folklore collectors encountered, but there is enough continuity to suggest that they are either the same or there was cultural drift that at least links the supernatural beings expressed in literature and oral tradition in the two periods. Some of the difference may also be the result of different forms of expression: medieval literate writers as opposed to illiterate nineteenth-century storytellers.

One the peculiar things about a certain type of supernatural beings is that regardless of the term used, they seem to hang together with a great deal of continuity. These are the elves (but we can also refer to them as fairies, sidhe, huldrefolk, or in parts of Scandinavia they are also called trolls). These entities are distinct in the way they are believed to live in communities with societies that roughly reflect the human condition. Outside of Britain, Ireland, Brittany, and Scandinavia (with some bleeding over into continental Europe and Russia), this idea is virtually non-existent. Supernatural beings playing the same part in similar legends are usually singular, or appear in pairs or threes - but they act singularly. It is reasonable to ask how this concept existed across linguistic lines in a well-defined geographic zone. If the idea diffused, why did it not diffuse elsewhere? Most folklorists would shun the explanation of diffusion because this perception of elves seems to be such a core perception of the supernatural world that it would be difficult for it diffuse: when it comes to folklore, stories travel easily, but they usually adapt to local belief systems rather than carry foreign belief systems with them.

So by way of not answering your question, we can describe this peculiar aspect of oral tradition related to elves, but we cannot say with authority were it originated. The question of origin for all the supernatural beings at the heart of your question is in a remote past that is difficult to describe or understand.

For sources: on trolls, a great piece of work is Elisabeth Hartmann, Die Trollvorstellungen in den Sagen und Märchen der Skandinavischen Völker (Tübingen: Eberhard Karls Universität Tübingen, 1936). In general, one of the most respected authorities on the question of Celtic and Scandinavian folklore is the late Bo Almqvist; see his Viking Ale: Studies on Folklore Contacts between the Northern and the Western Worlds (Aberystwyth: Boethius, 1991) edited by Éilís Ní Dhuibhne and Séamas Ó Catháin.

/u/sunagainstgold wrote a very nice post on the origins and influences of that very famous popularizer of "trolls, elves, dwarfs, etc": Tolkien. It will give you some helpful background into the origins and overlap of Northern European mythologies.

The trolls, elves, and dwarfs from Tolkien's books and resulting high fantasy works were heavily inspired by Germanic and Norse mythology. Norse creation stories and other mythology are documented in the Poetic Edda (compiled in the 13th century from earlier traditional sources) and the Prose Edda.

A dwarf (Old Norse: dvergr, Old English: dweorg, Old High German: twerg, Proto-Germanic: dwergaz) is a certain kind of invisible being in the pre-Christian mythology and religion of the Norse and other Germanic peoples. The dwarves are pitch-black in appearance and live underground in Svartalfheim, a place which was probably thought of as a labyrinthine complex of mines and forges. The dwarves are most often noted for being extremely skilled smiths and craftspeople. (Source ; This page has a cited list of primary sources.)

(edit: Not to go on a rant here, but this author uses a very literal interpretation of the text with which I don't personally agree. Many Norse academics and practitioners of the Norse religion believe that the places these beings lived in were meant to be interpreted as different dimensions, in a sense. Therefore, places like Svartalfheim weren't necessarily considered by the Norse to actually be underneath the physical Earth, but underneath it on a more spiritual plane. It was located on a lower branch of Yggdrasil, the tree of life, which had many branches in which nine different worlds sat, including our own.)

As you see, they were very similar in description to the dwarfs seen in popular modern fiction! As to where they came from, The Poetic Edda has some answers. (Ymir is the original jötnar, or giant, and a sort of magical creation deity.)

Then Bor's sons took Ymir and bore him into the midst of Yawning-gap, and made of him the earth; of his blood seas and waters, of his flesh earth was made; they set the earth fast, and laid the sea round about it in a ring without; of his bones were made rocks; stones and pebbles of his teeth and jaws and the bones that were broken; they took his skull and made the lift thereof, and set it up over the earth with four sides, and under each corner they set dwarfs, and they took his brain and cast it aloft, and made clouds.

The Elder Eddas of Saemund Sigfusson; and the Younger Eddas of Snorre Sturleson has a more detailed description of how the dwarfs were actually formed:

Then the gods, seating themselves upon their thrones, distributed justice, and bethought them how the dwarfs had been bred in the mould of the earth, just as worms are in a dead body. It was, in fact, in Ymir's flesh that the dwarfs were engendered, and began to move and live. At first they were only maggots, but by the will of the gods they at length partook both of human shape and understanding, although they always dwell in rocks and caverns.

I will come back and update in a reply to this comment with further info about the other mythical races you asked about if you're interested! :) In the meantime, I highly suggest Myths of the Norsemen: From the Eddas and Sagas if you're interested in learning more about Norse mythology. It's provided for free online by Project Gutenberg.

Honestly I didn't expect any responses so thanks for your replies, will be great reading them all.

Coming at the question from another direction, there is speculation that elf folklore may have been influenced by the individuals with Williams syndrome. This is a genetic disorder that results in elf-like facial features; small upturned nose, long philtrum (upper lip length), wide mouth, full lips, small chin, and puffiness around the eyes. It also results in various learning disabilities, paired with unusually high verbal and musical skills, and a very outgoing personality.

I don't know that this link could ever be more than speculative. I'm not sure this response meets the high standards for this subreddit. Apologies if it is found lacking.

Related (enough I hope) - where do the four Icelandic "guardians" fall in this .... taxonomy I guess. Are they considered troll/faye/etc or gods?