When speaking about the legendary and somewhat historically dubious times of the Kingdom of Rome, the first Pontifex Maximus was either Numa Marcius, the son of Marcius - one of the senators of the kingdom (if we believe Livy) or it was that of King Numa himself (if we believe Plutarch).
The first recorded person of the earliest days of the republic that we knew of who held the office of Pontifex Maximus was Gaius Papirius in the year 509 B.C who is said to have organized the college and religious institutions of Rome after that of king Numa.
However, that remains highly debatable and if somewhat dubious as most of the religious and historical records of Rome during 500-300 BC are sorely lacking and the records of the pontifex maximus (Annales maximi) that we know of were already faded, lost, destroyed or written over by the time historians such as Livy and Plutarch.
We can not be sure that Numa was an actual person or that he was ever a "Pontifex Maximus", some would argue against as pontifex literally means "bridge builder" and many scholars now believe originated as a psuedo-religious office that was in charge of maintaining Rome's oldest bridge the Pons Sublicius, then they got the charge of calendars and gradually other functions (like augury) that rose this office into prominence. This college of pontiffs were most likely advisors to the King and became more influential during the early republic jurisprudence and legality was in the hand of the college of pontiffs.
Coincidentally, the first rex sacrorum of the Republic - a religious title that technically outranked that of pontifex maximus as master of the rites but was seen with antipathy by the roman people (because of its king (rex) association) and unwanted by the ambitious patrician families (as it was politically useless) - was also of the gens Papirii.
There are arguments from some modern scholars that suspect that this isn't a matter of mere supreme religious prominence of the Papirii family but rather a sign of how unreliable our sources are and that this might in fact be a case of outright forgery and an act to rise its family to historic prominence (as was very valuable in Roman society) by that of Pontifex Maximus C. Papirius Maso in the mid-third century B.C.
Though this is not uncontested and it might be likely that the Papirii family just held great sway of the earlier religious institutions of the Roman republic. But it still gives us pause to consider how difficult it is to judge the historicity of what sources we have, when even the primary sources are lacking or dated 500 years after its actual time.
Hope that answers some of your questions!
Also: Complete side note but one could argue that the catholic church is actually the remaining roman institution that still exists to this day. The christians living under the Roman empire practically emulated quite a lot of roman administrative policies before and after their ascension as sole religion of the roman empire. An example to this would be the roman diocese which divided the empire into administrative regions which the roman christians adopted into their own system of organization. There are even examples of bishoprics and dioceses to this day that still retains its original, roman, borders.
sources
Glinister, F. (2017). Politics, power, and the divine: The rex sacrorum and the transition from monarchy to republic at rome: Journal of the australian society for classical studies journal of the australian society for classical studies. Antichthon, 51, 59-76. doi:http://dx.doi.org.pva.uib.no/10.1017/ann.2017.6
Forsythe, G. (2005). A critical history of early rome : From prehistory to the first punic war.
Retrieved from https://ebookcentral-proquest-com.pva.uib.no