These concepts all (with the exception of Dharma, which is sort of a Pan-Indian concept that's in all Indian religions) derive from the Shramanical tradition, which is a general term referring to those who became Śramaṇa (Samaṇa in Pali) which simply means an ascetic.
These ascetics formed a parallel system of religious thought of both the Veidic religion and the local folk religion focused on worshiping local Devas, Nagas, and Yakshas. The Shramanic tradition had a great deal of internal diversity, but the common denominator for most of these groups was a belief in repeated rebirth, Karma, an enlightened state in which one is free from this repeated rebirth, etc...
The Shramanical tradition even seems to have a sort of common vocabulary. If you compare the religious terminology of Buddhism and Jainism for example, you can see that often one religion uses as a standard term something that the other religion also uses in its terminology, although non-standard. For example, the Buddhist term for someone who has become freed from defilement and rebirth is the term Arahant, and Jainism occasionally uses the Ardhamagadhi equivalent term Arihant. In Jainism, the standard term for the same thing is Jina, which means "one who has achieved victory" which in Buddhism is a title of the Buddha.
Some terms are totally identical. Samsara, Karma, and Nirvana are common to both Buddhism and Jainism and are absent in the Brahmanical literature (e.g. the early Upanishads) from the same period, so logically, the commonality has to stem from their common non-Vedic source, which is their shared ascetic tradition.
We can see then that when the Buddha uses these terms he is adopting an idea that already existed and we can also see that he often gives them a radically new interpretation. In Jainism for example, Karma is imagined to be almost like an invisible sticky substance that sticks to your soul (called Jiva in ardhamagadhi) and causes suffering, and so the goal of Jain practice is to purge all karma through ascetic spiritual practice after which one's soul would ascend to a formless perfect heaven inhabited by disembodied souls. In contrast to this the Buddha defined the cause of suffering to be craving, and ultimately ignorance of reality, and emphatically insisted quite often:
"Intention, I tell you, is kamma. Intending, one does kamma by way of
body, speech, & intellect."
If you want some contempraneous sources on what some of the other Shramanical schools thought, the Samanaphala Sutta (http://www.accesstoinsight.org/tipitaka/dn/dn.02.0.than.html) has a listing of six such schools and their teachings. Note that Mahavira, the leader of the Jains, is given the name Nigantha Nataputta. Also, some of those groups believed some pretty far out things that aren't nessisarily representative of what all Shramanas thought, and in all likelihood the most outlandish aspects of their doctrines are stated in the most unappealing way possible so I wouldn't take it as an overly accurate depiction of some of the groups. You do clearly the common elements with some of them though, even in the more outlandish ones in that they were at least considering questions about rebirth and karma.