The idea is found in nuce the first time in the Epistula Apostolorum:
And behold a man shall meet you, whose name is Saul, which being interpreted is Paul: he is a Jew, circumcised according to the law, and he shall receive my voice from heaven with fear and terror and trembling. And his eyes shall be blinded, and by your hands by the sign of the cross shall they be protected (healed: other Eth. MSS. with spittle by your hands shall his eyes, &c.). Do ye unto him all that I have done unto you. Deliver it (? the word of God) unto the other.
Note that the epistle precedes Acts insofar :
- Acts doesn't explain why Saul is Paul
- The epistle explains that Saul "being interpreted is Paul".