It appears the Theophilus of Adana is, indeed, the first known instance of this myth. Dating the origin of the myth was a bit harder for me to establish.
It is claimed to have been written by Eutychianus of Adana, but the claim seems questionable to me, and, I've come to find out, others as well. "A Dictionary of Christian Biography, Literature, Sects and Doctrines" sources the story to the biography of Eutychianus of Adana (apparently a part of the Acta Sanctorum), but calls it's veracity into questions: "Cave, however, questions the authenticity of this biography."
The Sources of the Faust Tradition By Robert P. More, Philip M. Palmer state the the last paragraph of the translated story, which provides that accounting of authorship, was likely added by the story's scribe to help authenticity:
Most of the Theophilus scholars are of the opinion that Eutychianus was more probably a scribe who elaborated the original legend and added the final paragraph in order to make the whole more plausible.
The authors state the 6th century dating for the story is possible, but that the first version was probably written:
between 650 and 850 A.D.
With 850 AD being the approximate timing of a more readily verified latin translation, by Paulus Diaconus of Naples. The deal with the devil from this translation (then translated into english) in the same paper, is as follows:
The devil then said : "How shall I give help to him, a man serving his God? But if he will be my servant and be counter among out hosts, I will aid him so that he may do more than before and rule over all, even the bishop." And the perverted Jew said to the wretched steward : "Didst thou hear what he hath said to thee?" And he replied : "I have heard and whatsoever he shall say to me, I will do so long as he helps me." And he began to kill the feet of the prince and to implore him. The devil said to the Jew : "Let him deny the son of Mary and those things which are offensive to me, and let him set down in writing that he denieth absolutely, and whatsoever he may desire he shall obtain from me, so long as he denieth." Then Satan entered into the steward and he replied : "I deny Christ and His mother." And making a written statement and putting wax on it, he sealed it with his own ring and the two went away rejoicing greatly at his perdition.