This question could be paraphrased in this way: when did birthday celebrations become a widespread thing?
In the Bible, at least, "birth days" are recorded only twice. The first was in the Old Testament (Pharaoh, from the Moses story in Exodus), and the second was in the New Testament (King Herod).
Generally, birthdays were celebrated by pagan societies. As astronomers, astrologers, scribes, and other officials developed more complex and accurate calendars, the dates associated with chieftains and monarchs were more heavily scrutinized. Birthdays were associated with movements in the Heavens, weather, and other related omens. And, especially with royalty, birthdays usually involved great celebrations.
In the fifth century BC (BCE) the Greek historian Herodotus briefly described elements of Persian and Egyptian birthday customs. Families, rich and poor, usually set aside a sum of money to celebrate birthdays with animal sacrifices. The scope of these celebrations was obviously different depending on your class.
In Greece, however, celebrating your birthday each year didn't seem to be a major priority. Wealthier families usually had a feast/party when a baby was born, when the child "came of age", and after the person died.
Rome, as usual, adopted elements of Greek birthday customs and turned things up a notch. Emperor Caligula celebrated his daughter's first birthday by publicly slaughtering almost a thousand animals and hosting massive chariot races. This is all for a little girl who couldn't walk or talk yet. I imagine the after party would have been something to see.
Also, birthdays are not the only option. In many parts of Europe, people celebrated name days. It was a common Christian practice to give every child a saint's name, and then that person would celebrate their name day on the feast day of that saint. Given that births of ordinary people weren't tracked that closely until the 20th century, a person might not necessarily have known exactly when their own birthday was. With name days, everybody still got a yearly celebration!
There's a tablet, part of the Vindolanda tablets held in the British Museum, that talks of an invitation to a birthday party around the year 100AD in Roman Britain. A translation given by Oxford:
"Claudia Severa to her Lepidina greetings. On 11 September, sister, for the day of the celebration of my birthday, I give you a warm invitation to make sure that you come to us, to make the day more enjoyable for me by your arrival, if you are present (?). Give my greetings to your Cerialis. My Aelius and my little son send him (?) their greetings. (2nd hand) I shall expect you, sister. Farewell, sister, my dearest soul, as I hope to prosper, and hail. (Back, 1st hand) To Sulpicia Lepidina, wife of Cerialis, from Severa."
It is uncertain when birthday celebrations became common. But we know that it goes back quite a ways. "Natalis" and "natalicium" were used by the Romans to denote what we call a birthday. Also the Greek words "genesia" and "genethlios" were similarly employed. In both Greek and Latin a certain extension of this primitive use seems to have taken place even in pre-Christian times. In Latin natalis apparently came, at least sometimes, to mean little more than "anniversary", and it was used of the accession day of the emperor as well as his birthday.
As for birthdays being primarily pegan, as CosmoDanger points out, that is not exactly true. Because "Natalis" has such of a broad meaning, it is confusing when Origen wrote "of all the holy people in the Scriptures, no one is recorded to have kept a feast or held a great banquet on his birthday. It is only sinners (like Pharaoh and Herod) who make great rejoicings over the day on which they were born into this world below" (Origen, in Levit., Hom. VIII, in Migne P.G., XII, 495). We cannot entirely eliminate the doubt whether at the introduction of Christianity "genethlios" and "natalis" had not already come to mean little more than "anniversary" or "commemoration rite". Ambrose (Serm. 57, de Depos. St. Eusebii) declares that "the day of our burial is called our birthday (natalis), because, being set free from the prison of our crimes, we are born to the liberty of the Saviour", and he goes on "wherefore this day is observed as a great celebration, for it is in truth a festival of the highest order to be dead to our vices and to live to righteousness alone." So we see that Christians of Smyrna about A.D. 150 write to describe how they took up the bones of St. Polycarp, "which are more valuable than precious stones and finer than refined gold and laid them in a suitable place, where the Lord will permit us to gather ourselves together, as we are able, in gladness and joy and to celebrate the birthday of his martyrdom". Birthdays in Christianity were celebrated along with the day they died, but the celebration date was often on the day of their birth into the world (C.I.G. 3417, and Rhode, Psyche, 4th ed., I, 235). So Christians celebrated birthdays, but not in the same sense that pagans did.