One inference that very clearly emerges out of 6th to 10th century copper plates of pallavas, cholas and pandiyas is that they - or probably the poets who wrote the prasashtis - want to take back the origin of the royal clan to sun moon and ramayana - mahabharatha characters. But evidently this is not supported by sangam literature and hence needs to be discarded.
Pandiyas were one of the earliest tribal groups of tamilnadu to emerge and establish probably one of the earliest kingdoms of tamil land. Their area of dominance was south tamil nadu - covering geographies which are now under the sea. For our sake let us call it greater tamilnadu or kumari kandam.
Mention is made about the pandiya in Valmiki raamayana. I don't have the exact verse offhand but it talks about the grand fort in the capital of pandiyas - probably the old madhura which was lost in sea.
In vyasa bharatha, arjuna seems to have married a pandiya princess.
Ashokan edicts mention pandiyas along with sathiyapuddhos who are considered to be adiyamans.
In later day copper plate grants (The Bigger and smaller chinnamannur grants, Velvikkudi grants etc) many mythical events of early pandiyas are listed.
The sangam literatures talk of few pandiyan kings. One of the earliest is the nilamtharu thiruvir paandiyan alias vadimbalam nindra paandiyan According to panambaaranar's thogaippayiram for tholkappiyam, tholkappiyar staged his work in this king's court.