Actually, we don't know that his name was changed at all. He may have had both names to start with as per the custom of his day as both a Jew by blood and a Roman citizen. After his conversion and change of direction he seems to have decided his other name was a better moniker.
Many mistakenly assume the Lord changed Saul's name to Paul sometime after Saul converted from Judaism to Christianity, which happened during his encounter with Christ on the Road to Damascus (Acts 9:1-19). Unlike the instance of Jesus changing Simon's name to Kepha (Gk. Petros) as a way of signifying the special role he would play in the Church (Mt 16:18, Jn 1:41-42), in Paul's case there was no name change.
Saul of Tarsus was born a Jew, "circumcised on the eight day, of the race of Israel, or the tribe of Benjamin, a Hebrew of Hebrew parentage, in observance of the law a Pharisee" (Phil 3:5). The Hebrew name given him by his parents was Saul, but, because his father was a Roman citizen (and therefore Saul inherited Roman citizenship), Saul also had the Latin name Paul (Acts 16:37, 22:25-28), the custom of dual names being common in those days. Since he grew up in a strict Pharisee environment, the name Saul was by far the more appropriate name to go by. But after his conversion Saul determined to bring the gospel to the Gentiles, so he dusted off his Roman name and became known as Paul, a name Gentiles were accustomed to.
The suggestion that the confusion is born out of having had multiple names from birth is born out by other sources such as Protestant writer F.F. Bruce, although his conclusion is that both names would have continued in use and it is only the preference of the NT writers in which we see a change.
He was born into an orthodox Jewish family, and as his father was a Roman citizen, he inherited this distinction, a rare one among eastern Jews. In Jewish circles he bore the name of Saul, but in the Gentile world he was commonly known by his Roman cognomen Paullus, Anglicized as Paul [...]
Saul’s father was a Roman citizen… [so] Saul was born a Roman citizen… As a Roman citizen, he had a Roman name, consisting of three parts: praenomen, nomen gentile and cognomen.2 What his praenomen (first or personal name) and nomen gentile (family name) were we can only guess; his cognomen, however, was Paullus, by which (in its English form Paul) we usually call him.
In family circles, however, he was known by his Jewish name Saul.
2. The threefold Roman name may be illustrated from the full names of such famous Romans as Gaius Julius caesar, Marcus Tullius Cicero, Lucius Cornelius Scipio.
(source: F. F. Bruce, The Spreading Flame)
In any event, we do not have a Scriptural source for the why and how of the name change. The most direct hint we have is the one you mention in Acts that simply notes he was "also known as". This is combined with the references to him by both names and and our own deductions from the correlation in how he was generally referred to before and after his life changing encounter with the Christ he had been persecuting.