Is there a similarity in shamanism and/or invention of nature magic/deities?
Maybe not, but there are interesting looking similarities. 
Frome the picture above:
1. First is “The Sorcerer” cave art shaman, 14,000–13,000 years ago, (France)
*Certain scholars question the validity of the sketch, claiming that modern photographs do not show the famous antlers. However, “The Sorcerer” is composed of both charcoal drawings and etching within the stone itself. Details, such as etching, are often difficult to view from photographs due to their size and the quality of the light source. Prominent French prehistorian Jean Clottes asserts that the sketch is accurate (‘I have seen it myself perhaps 20 times over the years’).
2. Next, is a female shaman, 9,000-8,500 years ago, (Germany).
3. Then, “Shiva Pashupati” Indus Valley Civilization (Indian) Shamanism 4,600–3,900 years ago
4. Then “Gundestrup cauldron” European (found in Denmark, made in Bulgaria or Romania) Shamanism 2,200–1,700 years ago
5. Then, in 1692 is the earliest known depiction of a Siberian shaman, (Samoyedic- and Tungusic-speaking peoples). refrefrefref

Shamanism encompasses the premise that shamans are:

intermediaries or messengers between the human world and the spirit worlds.

shaman is someone who is regarded as having access to, and influence in, the world of benevolent and malevolent spirits, who typically enters into a trance state during a ritual, and practices divination and healing. The word “shaman” probably originates from the Tungusic Evenki language of North Asia. According to ethnolinguist Juha Janhunen, “the word is attested in all of the Tungusic idioms” such as NegidalLamutUdehe/OrochiNanai, Ilcha, OrokManchu and Ulcha, and “nothing seems to contradict the assumption that the meaning ‘shaman’ also derives from Proto-Tungusic” and may have roots that extend back in time at least two millennia. The term was introduced to the west after Russian forces conquered the shamanistic Khanate of Kazan in 1552. The term “shamanism” was first applied by Western anthropologists as outside observers of the ancient religion of the Turks and Mongols, as well as those of the neighbouring Tungusic and Samoyedic-speaking peoples. Upon observing more religious traditions across the world, some Western anthropologists began to also use the term in a very broad sense, to describe unrelated magico-religious practices found within the ethnic religions of other parts of Asia, Africa, Australasia and even completely unrelated parts of the Americas, as they believed these practices to be similar to one another. Mircea Eliade writes, “A first definition of this complex phenomenon, and perhaps the least hazardous, will be: shamanism = ‘technique of religious ecstasy‘.” Shamanism encompasses the premise that shamans are intermediaries or messengers between the human world and the spirit worlds. Shamans are said to treat ailments/illness by mending the soul. Alleviating traumas affecting the soul/spirit restores the physical body of the individual to balance and wholeness. The shaman also enters supernatural realms or dimensions to obtain solutions to problems afflicting the community. Shamans may visit other worlds/dimensions to bring guidance to misguided souls and to ameliorate illnesses of the human soul caused by foreign elements. The shaman operates primarily within the spiritual world, which in turn affects the human world. The restoration of balance results in the elimination of the ailment. Beliefs and practices that have been categorised this way as “shamanic” have attracted the interest of scholars from a wide variety of disciplines, including anthropologists, archaeologists, historians, religious studies scholars, philosophers and psychologists. Hundreds of books and academic papers on the subject have been produced, with a peer-reviewed academic journal being devoted to the study of shamanism. 

Regional variations of Shamanism

“shamanist” Believe in spirit-filled life and/or afterlife can be attached to or be expressed in things or objects and these objects can be used by special persons or in special rituals can connect to spirit-filled life and/or afterlife (you are a hidden shamanist/Shamanism: an approximately 30,000-year-old belief system) there is what is believed to be a female shaman burial with a matching carved ivory female head belonging to the Pavlovian culture  29,000 to 25,000 a variant of the Gravettian/(Gravettian culture 33,000 to 22,000 years ago), dated to 29,000 to 25,000-years old Dolní Vestonice, Moravia, Czech Republic. A carved ivory figure in the shape of a female head was discovered near the huts. The left side of the figure’s face was distorted image is believed to be a description of elder female’s burial around 40 years old, she was ritualistically placed beneath a pair of mammoth scapulae, one leaning against the other. Surprisingly, the left side of the skull was disfigured in the same manner as the aforementioned carved ivory figure, indicating that the figure was an intentional depiction of this specific individual. The bones and the earth surrounding the body contained traces of red ocher, a flint spearhead had been placed near the skull, and one hand holding the body of a fox. This evidence suggests that this was the burial site of a shaman. This is the oldest site not only of ceramic figurines and artistic portraiture but also of evidence of early female shamans. Archaeologists usually describe two regional variants: the western Gravettian, known namely from cave sites in France, Spain and Britain, and the eastern Gravettian in Central Europe and Russia. The eastern Gravettians — they include the Pavlovian culture — were specialized mammoth hunters, whose remains are usually found not in caves but in open air sites. The origins of the Gravettian people are not clear, they seem to appear simultaneously all over Europe. Though they carried distinct genetic signatures, the Gravettians and Aurignacians before them were descended from the same ancient founder population. According to genetic data, 37,000 years ago, all Europeans can be traced back to a single ‘founding population’ that made it through the last ice age. Furthermore, the so-called founding fathers were part of the Aurignacian culture which was displaced by another group of early humans members of the Gravettian culture. Between 37,000 years ago and 14,000 years ago, different groups of Europeans were descended from a single founder population. To a greater extent than their Aurignacian predecessors, they are known for their Venus figurinesrefrefrefref

Religion Progression to me:
1. Animism (belief in a perceived spirit world) possibly by at least 100,000 years ago “the primal stage of early religion”
2. Totemism (belief that these perceived spirits could be managed with created physical expressions) possibly by at least 50,000 years ago “progressed stage of early religion”
3. Shamanism (belief that some special person can commune with these perceived spirits on the behalf of others by way rituals) possibly by at least 30,000 years ago
4. Paganism “Early organized nature-based religion” mainly like an evolved shamanism with gods (possibly by at least 13,000 years ago).
5. Institutional religion “organized religion” as a social institution with official dogma usually set in a hierarchical/bureaucratic structure that contains strict rules and practices dominating the believer’s life. And to me paganism and Institutional religion categorized into the following stages:
 *primal stage of organized religion is 13,000 years ago.
*proto-stage of organized religion is around 10,000 years ago.
*progressed stage of organized religion is around 7,000 years ago.
*developed stage of organized “Institutional” religion is around 5,000 years ago.

So, it all starts in a general way with Animism (theoretical belief in supernatural powers/spirits), then this is physically expressed in or with Totemism (theoretical belief in a mythical relationship with powers/spirits through a totem item), which then enlists a full-time specific person to do this worship and believed interacting Shamanism (theoretical belief in access and influence with spirits through ritual), and then there is the further employment of myths and gods added to all the above giving you Paganism (often a lot more nature-based than most current top world religions, thus hinting to their close link to more ancient religious thinking it stems from). My hypothesis is expressed with an explanation of the building of a theatrical house (modern religions development).

Sky Burials: Animism, Totemism, Shamanism, and Paganism

The Venus of Galgenberg

The Venus of Galgenberg is a Venus figurine of the Aurignacian era, also known in German as the Fanny von Galgenberg, discovered close to Stratzing, Austria, not far from the site of the Venus of Willendorf, a Venus figurine estimated at 30,000 years ago found at a paleolithic site near Willendorf, a village in Lower Austria carved from non-local oolitic limestone tinted with red ochre. The Venus of Galgenberg is a figurine of a woman weighing 10 g and made of greenish, very shiny amphibolite slate, the upper body is turned to the side, in a dancing position, three-dimensional front, flat back, believed to have had cultic or religious significance. The stone material is from the immediate vicinity of where the figurine was found, and the waste material provides proof that the figurine was made in the same area. Bones of horses and mammoths, as well as antlers, were found. Charcoal samples made an exact determination of the age of the finds using radiocarbon dating possible. This method resulted in an age of approximately 32,000 years for the Statuette. 11 fire places. Dating: between approx. 33,000 and 28,000 BP. The occurrence of amphibolite schist at a distance of several hundred metres from the site, as well as many small fragments of this raw material in the area of the fragments of statuette, which may be waste from the original carving, support this assumption. The statuette itself is an upright standing figurine without feet, one leg touching the other at the feet. The legs are separated by a pointed oval perforation.  refref