This is all sourced from "Mesopotamia: the Invention of the City" by Gwendolyn Leick.

The earliest Mesopotamia records include a number of titles, both religious and secular (although the distinction between those is less clear than it would be today). The word "lugal" is used to refer to the king, with modifiers to indicate their influence ("King of Kish" (Kish being an important city) was commonly used by kings wanting to assert that they ruled not just their city or region but the whole of the area under control of the Akkadian (or Sumerian, etc.) empire. This isn't just a word that was used to refer to them, but was actually incorporated into names, such as "Lugalzagesi", an early king.

The title "en" was used for the primary religious leader, and this predates the use of "lugal" and initially had both religious and political implications. There was also a female equivalent, referred to as "nin".

In addition to these titles, there are also records of lower official titles, such as "ugula" and "nimgir", which were in charge of various levels of the administrative bureaucracy.

These are going to be the oldest titles of which there are records, as they are from what are effectively the earliest records. I feel safe saying that titles existed prior, but it's obviously not substantiatable without records.

Sorry to take so long! The oldest recorded titles are those found on the early administrative tablets from Uruk and the so-called "Lexical lists", and especially the lexical list Lu A, probably one of the cuneiform texts with the longest history of copying. These texts were essential massive lists of everything-job titles, birds, fish, kinds of vessels, kinds of wooden objects, and so on ad nauseam, to be copied by trainee scribes. Lu A was a lexical list of a large number of professions, most of which were not recorded by the contemporary administrative records. So it seems that the goal of the lists was to provide a comprehensive list of all possible job titles imaginable rather than a simple copylist for students. Even more interestingly, they use the cuneiform sign NAM2 rather than the LUGAL or EN we would expect from other Sumerian texts and it cannot be an unrelated title because the sign NAM2 is glossed as šarru along with more typical titles such as SANGA, one of a class of priests; perhaps in this case the lexical list preserves an alternate logogram or title.

Caesar is a pretty old one, and gave birth to kaiser, tsar, as well as the anglicized czar still used in the United States government. Originally just part of Julius Caesar's name, it became synonymous with "emperor" and spread from Rome to other cultures. It's ~2000 years old.

I expect variants of "priest" and "chief" in their respective languages would be amongst the oldest; Kohen is priest in Hebrew, for example.