Where is the first historical reference of the cycle of existence, according to the scriptures ?
According to the timeline of Hindu texts, based on (historical) dating:
The oldest scripture still extant is Rig Veda Samhita, whose composition is usually dated to roughly between 1800 – 1100 BCE. There is a debate on whether there is a mention of multiple rebirths in Rig Veda Samhita. If we consider the implicit mentioning, then Rig Veda is the first scripture that talks about multiple rebirths.
So, it is clear that the first reference of multiple rebirths is up to the interpretation.But the first clear and direct reference of multiple rebirths is as early as 1200 - 800 BCE.
It is also important to note that there is no absolute dating for Vedas.