The Kathāvatthu is a para-canonical text of the Theravada Abhidhamma Pitaka attributed to Moggaliputtatissa which is traditionally said to originate at or around the time of King Ashoka, but this date is highly contested. There is speculation that this text was itself composed over a lengthy amount of time and not all at once, but generally the first chapter/controversy over a person (puggala) is considered the earliest. There is an auto-commentary to this text - also traditionally attributed to Moggaliputtatissa - and it is thought given the structure of the text and the commentary that they were created at the same time. To find out more about the history of this text (what is known versus what is speculated) I would recommend Venerable Sujato’s excellent article.
In chapter 1.1 of the Kv we find this at the end:
Theravādin: … again, it was said by the Exalted One:
“There are these three teachers, Seniya, to be found in the world—who are the three? There is first, Seniya, that kind of teacher who declares that there is a real, persistent soul in the life that now is, and in that which is to come; then there is the kind of teacher, Seniya, who declares that there is a real, persistent soul in the life that now is, but not a soul in a future life; lastly, there is a certain teacher who does not declare that there is a soul either in the life that now is, nor in that which is to come. The first, Seniya, of these three is called an Eternalist, the second is called an Annihilationist; the third of these, he, Seniya, is called the teacher, who is Buddha supreme. These are the three teachers to be found in the world”.
Is the Suttanta thus?
Theravādin: … again, did the Exalted One speak of “a butter-jar”?
Theravādin: Is there anyone who can make a jar out of butter?
Puggalavādin: Nay, that cannot truly be said … .
Theravādin: … finally, did the Exalted One speak of an oil-jar, a honey-jar, a molasses-jar, a milk-pail, a water-pot, a cup, flask, bowl of water, a “meal provided in perpetuity”, a “constant supply of congey”?
Theravādin: Is there any supply of congey that is permanent, stable, eternal, not liable to change?
Puggalavādin: Nay, that cannot truly be said … .
Theravādin: Hence it is surely wrong to say “the soul is known in the sense of a real and ultimate fact”.
The bold is mine. I emphasize this because the explanation for this obscure passage is found in the auto-commentary. The auto-commentary to the Kathāvatthu was published in 1940 by the Pali Text society and translated into english by BIMALA CHURN LAW, Ph.D., M.A., B.L. Here is a library reference to the text.
Here is that section of text which I’m typing out as I only have hard copy pictures of the 1940 text in question on pages 41 through 43:
“ Did the Exalted One speak of a butter-jar ?” and the
following are adduced to show that meaning is not always
according to the form of what is said. A jar made of gold is
called a golden jar, but one made of butter is not in the
same way called a butter-jar. What is meant here is this: a
butter-jar is only that wherein butter is put. In regard to an
oil-jar, and so on, this is the sense. A (‘ permanent ’) meal or
a congey is not eternal and permanent as is nirvana. ‘ A meal
provided in perpetuity, a constant supply of congey ’ implies
the sense that we are to give in charity every day without
any limit of time.
Even in such expressions as ‘ there is the person who works
for his own good and so on, there is no such person as
bodily and mental aggregates, known in their specific and
general senses. Given bodily and mental aggregates, it is
customary to say such and such a name, a family. Thus, by
this popular turn of speech, convention, expression, is meant:
“ there is the person.” This is the sense here. Hereon it was
also said  by the Exalted One: “ These, Cilla, are merely
names, expressions, terms of speech, designations in common
use in the world.’’’^ What is meant here is: even without
reference to bodily and mental aggregates the term ‘ person ’
is used to denote a popular convention in both its specific
and its general sense. The Buddhas have two kinds of
discourse, the popular and the philosophical. Those relating
to a being, a person, a deva, a ‘ brahma and so forth, are
popular discourses, while those relating to impermanence,
ill, soul-less, the aggregates, the elements, the senses, the
application of mindfulness, the intent contemplation, and so
forth, are discourses on highest meaning. Therein, in the
popular discourse, when there is speech of a being, a person,
a deva or brahma, he who is able to understand, comprehend
its meaning, or get out (of this world), or attain the victory
of an arahan, him the Exalted One teaches, at the very
outset, about a being, a person, a man, a deva or a brahma.
He who, on hearing differently in discourse on highest meaning
about impermanence, or ill, or the like, is able to understand,
comprehend its meaning, or get out (of this world), or attain
the victory of an arahan, him (the Exalted One) teaches
differently about impermanence, and so forth. Thus, he
does not teach at first the highest-meaning discourse to any-
one, even to one who understands him in popular discourse.
Taking his stand on popular discourse he, on the other hand,
teaches the highest-meaning discourse afterwards. He does
not teach at first popular discourse to one who can understand
him in highest-meaning discourse. On the other hand,
having enlightened him in highest-meaning discourse, he
teaches popular discourse afterwards. Highest-aim dis-
course is, as a rule, too severe to begin with; therefore
the buddhas teach at first by popular discourse, and then
highest-meaning discourse. But popular discourse they teach
consistently and in conformity with truth according to the
method selected. And highest-meaning discourse, too, ‘they
teach consistently and in conformmity with truth according to
the method selected.’
Thus it is said:
The Enlightened One, best of speakers, spoke two kinds of
truth, namely, the popular and that of highest meaning, a
third is not got at.
Therein, discourse meeting with agreement is true and is
by way of world convention. Highest-meaning discourse
expression is also true and, as such, characteristic of things
(as they are).
There is another way of putting it. The teaching of the
Exalted One is of two kinds, the highest-meaning teaching
consisting of the aggregates, and so forth, and the popular
teaching consisting of ‘butter-jar,’ and so forth. The Exalted
One does not, indeed, overrun consistency. Hence, on
the mere expression “there is the person who,” must not
command adherence. The highest meaning has been declared
by the Teacher, without transgressing the concept. So,
another wise man also should not, in explaining the highest
meaning, overrun a concept.
The remaining meanings are clear everywhere.
The controversy on ‘person’ is ended.
The translation in english is very old and unfortunately I have not been able to find a pali version of this auto-commentary. However, the second part I marked in bold above I have been able to find the pali and here it is:
The Enlightened One, the best of teachers, spoke of two truths, conventional and ultimate; no third is described. Conventional truth is known through agreement and ultimate truth discloses phenomena as they actually are.
Duve saccäni akkhäsi Sambuddho vadatam varo
sammutim paramatthan ca tatlyam nüpalabbhati
sanketavacanam saccam lokasammutikäranam
paramatthavacanam saccam—dhammänam tathalakkhanam
The english above is my rudimentary translation informed by ChatGPT and my own understanding. The pali text comes from “Early Buddhist Theory Of Knowledge” by K. N. JAYATILLEKE B.A.(Ceylon), M.A.(Cantab), Ph.D.(London) 1960 page 363. Here is a reference to the text. I would welcome other experts in pali to give a better translation.
So the earliest description of the two-truths doctrine that I’m aware of in any Buddhist text is from this para-canonical Theravada text and its auto-commentary although the date is very uncertain. I’d also note that the text in question above is immediately preceded by a quote from the Vajira sutta marking it as evoking an early EBT teaching.
Although this was not the point of this thread, I hope this is helpful in answering questions that were raised.