I first wanted to address this sentence:

already existing concerns in the Upanishads and the Vedic period

The Vedic period could be considered from 1500 BCE to 500(ish) BCE should be seen as separate from the era that produced the Upanishads.

The axiomic ideas in shramanic thought such as karma, rebirth and liberation have little to no source in classical Vedic literature and culture. These are new philosophical ideas that date from the shramanic period and likely influenced the authors of the Upanishads and not the other way around. It is difficult to date the Upanishads and some (most?) modern scholarship increasingly dates them after or contemporary with the shramanic period. Most general history and older scholarly works claim that shramanic religions rose out of a vedic/upanishadic context but I don't see this as being true. Johannes Bronkhorst in "Greater Magadha: Studies in the Culture of Early India" probably makes the best case for later Upanishad dating and I agree with his logic (though not necessarily the overall thesis of that book but that is another topic).

What changed in society that allowed these heterodox religious movements to arise and gain prominence?

We don't really know alot about the culture that produced the shramanic religions. The "native" culture of India was the Indus River Civilization that existed from around 2600 BCE to 1900 BCE. One extremely interesting artifact from this period are seals/stamps that depict some sort of priest/shaman sitting in a full lotus-like meditation posture. This strongly indicates that some sort of yogic tradition dates from this period and can likely be seen as indigenous practice. We dont know if the ideas of karma, rebirth and liberation also are part of the indigenous practice or if they developed later. But it is very interesting that the underlying physical practice of formal, seated religious practice dates from this period.

It would seem that the Indus River Civilization was already in decline when an ethnolinguistic group that spoke Indo-Aryan languages migrated into (invaded?) the Indian subcontinent. They were horseman with superior military power and became politically dominant in portions of India. They brought with them a polytheistic religion based on a priestly caste that performed elaborate rituals as a their primary form of religious worship. As already mentioned, the core tenants of shramanic religions are not found in Vedic literature and in many ways the Vedic literature contradicts shramanic ideas. One example being ideas of the afterlife.

Shramanic religions had their genesis approximately around 500 BCE. We unfortunately can say little about this period in the Gangetic Plain where these traditions originated. Writing was essentially non-existent and the archaeological record is only slightly revealing. Much of what is stated about this period comes from religious texts that date from a much later era. One thing that does seem for certain was this was an era of increasing urbanization. The core driver of all periods of increasing urbanization is an increase of agricultural efficiency. This was a period of increased usage of iron and iron tools made it much easier to engage in deforestation and field plowing. One hallmark of increased agricultural production is food surpluses that allow for greater cultural diversification. I feel this increased urbanization and the underlying agricultural surpluses influenced the development of Shramanic religions in three ways:

1. The core aspect of all Shramanic religions is the ideal of an ascetic lifestyle where the practitioner ceases any activity that benefits society with any economic output and instead lives a largely homeless existence that is dependent on other productive members of society for sustenance. This could only happen in a society with a good amount of agricultural surpluss to begin with and thus was dependent on the precondition of increased agricultural productivity.

2. As the Gangetic Plain saw increased agricultural productivity and urbanization, this resulted in increased trade and merchant activity. Cultural and religious ideas are often spread via trade routes and as this area had increased trade, it developed the infrastructure for ideas and practices such as Shramanism to disseminate quickly.

3. As the urbanization accelerated it led to increasingly large political/military empires that had the ability to adopt religions in an official capacity and this would of course greatly speed adoption and propagation of these traditions and philosophies. Both Jainism and Buddhism saw periods of official imperial support and this was instrumental in them becoming widely disseminated and popularized.

Materially the Indian Second Urbanization is the backdrop to the emergence of Buddhism, Jainism, and the other sramana-like schools that are recorded in their canons. The Vedic Period likely reflects life in India after the decline of the Indus Valley/Harappan civilization when the urban centers of the Indus Valley had been abandoned due to drought, and/or climate change and invasion, and it took close to a millennium for new urban centers to emerge in the upper Gangetic plain.

All of the sramana movements relied on a surrounding community that produced excess goods- their clothing came from cloth that was discarded, donated, or used for funerary purposes, and their food came from excess food in the community that was donated to ascetics in the hope of good karma. This kind of lifestyle can't really exist in an organized way in a subsistence agrarian society where people don't produce much more than they consume- to feed wandering monks much less endow monasteries and serve communal meals, you need excess production, possibly controlled by a local elite.

Politically, India was very fragmented at this time, with many small kingdoms and numerous different forms of government. Scholars of the social sphere of the era of Mahavira and Shakyamuni talk about the existence of 'tribal republics' and monarchist city-states that were controlled by kings. The tribal republics, which seems to be where Shakyamuni was born, didn't have centralized states and may have reflected non-Vedic cultures that immigrated from outside India, or might have been indigenous cultures that were resisting an urbanizing influence that ultimately originated with the Indus Valley culture.

In the northwest, you also have particular influence from at least two cultural groups from outside India- Persia, which has some very similar beliefs to a lot of Brahmanism and speaks a related language, and semi-nomadic groups that are moving in and out from Central Asia. Shakyamuni's ancestors are thought by some to have been derived from this second group, and it may have been a long-term source of non-Vedic thought. There is also no real consensus on what language and religion was part of the Indus Valley civilization- it might have been a conduit for other influences from outside, even if it was an indigenous culture, simply because of trade and other relations that developed.

So it really isn't correct to think of India before the Sramanas as a culturally uniform area that then suddenly spawned a number of distinctive philosophies. Instead, you have lots of regional and cross-cultural traditions that are in dialogue and competition with one another, with no strong central authority that can control which views spread and which views are repressed. The Second Urbanization creates an environment where a lot more religious and philosophical specialists can be supported, and where transportation between population centers made the spread and cross-fertilization of different movements a possibility.

Around the time of Shakyamuni, there seems to have been a process of consolidation happening, seen in the military campaigns of Ajatasatru that are described in the sutras. This process eventually lead to the emergence of the Mauryan Empire of Ashoka, which is really where our substantive knowledge of the Sramana tradition originates.

At this point, India starts to have a strong central state, but one that seems to take a very broad view of religion and the sramana tradition. Ashoka makes pilgrimages to Buddhist cites and erects monuments, but he and his successors seem to be broadly supportive of the sramana movement, donating land and food, erecting shelters and monasteries. Only at this stage do we start to see (in the literary record- we don't have archaeological evidence here) kings and emperors getting involved in doctrinal disputes, with the law-enforcement power of the king being used by factions within the sramana movement to purge dissident or heterodox elements.

In the Ashokan era, to the average person there may not have seen much difference between a Buddhist monk, a Jain monk, and a Vedic Brahmin who practiced ascetic austerities. They lived similar lifestyles and were distinguished by the type of stories and verses they recited. Monks from multiple traditions may have gathered at shelters constructed by wealthy donors, and lay donors like kings might have patronized teachers from many different traditions. Ashoka and his successors may have taken a very broad view of religion because this was what made it possible to unite a large empire that had a lot of different religious communities.

Sources:

Uma Chakravarti's book The Social Dimensions of Early Buddhism is one good source of information about the material and political environment of Second Urbanization India. Steven Collins Nirvana and other Buddhist Felicities contains some information about how the material conditions of ancient India shaped the social environment.