Suniti Kumar Chatterji, the eminent linguist, has said that the concept of Puja is a distinctive contribution of the Dravidians.
It occurs in the Bhagavad Gita in a general sense
Bhagavad Gita Chapter 2 Verse 4 भगवद् गीता अध्याय 2 श्लोक 4
अर्जुन उवाच कथं भीष्ममहं संख्ये द्रोणं च मधुसूदन। इषुभिः प्रतियोत्स्यामि पूजार्हावरिसूदन।।2.4।।
English Translation - Swami Gambirananda
2.4 Arjuna said O Madhusudana, O destroyer of enemies, how can I fight with arrows in battle against Bhisma and Drona who are worthy of adoration?
But where does it occur first to denote the formal act of worship as performed contemporarily?