The significance of these two names must very much depends on whether there really was a name change from Saul to Paul, or whether Paul was given a Jewish name and a Greek or gentile name as a child - not an uncommon practice among the Jews. On the other hand, it was also quite common, even in Palestine, for Jews to be known only by a Greek name. Examples include Aristobulus, Antigonus, Philo of Alexandria, who certainly appear to be from devout Jewish families.
In Acts of the Apostles the change of usage from Saul to Paul is so immediate and dramatic that one could almost expect the author to allude to Saul's decision to change his name if indeed this is what happened. However, I question why Saul would have wanted to abandon his birth name, given that in his epistles Paul consistently describes himself as a proud Jew, going so far as to say that his greatest wish was to convert the Jewish nation (see Romans 11; 1 Corinthians 9:20).
Instead of suggesting that Saul actually changed his name to Paul, Acts 13:9 merely tells us that Saul "also is called Paul." The change of name reference does not begin with Saul's conversion to Christianity on the road to Damascus but much later in Cyprus (Acts 13:9). If Saul had always had both names, there may have been theological reasons for the author of Acts to refer to him as Saul before the miracle that occurred in Cyprus and to call him Paul from that point forward.
Interestingly, Paul never mentions the name Saul in his own epistles, consistently maintaining the name Paul, even when he writes of persecuting the Christians, of his conversion and of his early mission. It is as if he had never used that name or that he was ashamed of it, yet we know he was a proud Jew.
Josephus (Antiquities XX.9.4) talks of a Saulus, a disreputable member of the Herodian family, who used violence with the people and was very ready to plunder those that were weaker than himself. Robert Eisenman, in The Dead Sea Scrolls and the First Christians, sees significance in this name, for the account in Acts of the Apostles. He says (page 242) that directly following the stoning of James, Josephus described Saulus and Costobarus leading a band of thugs in rioting in Jerusalem, which seems to have involved stealing the tithes of the Poorer Priests on behalf of the Rich High Priests. Josephus has Saulus go to see Nero in 66 CE, to inform him of the situation in Palestine, and Eisenman sees a parallel in Acts, where Paul was sent to Nero in 60 CE, when he appealed against trial in Judea. Eisenman suggests the parallels a so strong that Paul and Josephus' Saulus may have been the same man, but this is unlikely because Paul probably went to Rome before 66 CE and there is nothing we know about Paul to suggest that he was in any way a disreputable person.
If the author of Acts intentionally associated the apostle Paul with Saulus, what would the reason have been? Scholars have long noticed irreconcilable differences between Paul’s epistles and corresponding accounts in Acts of the Apostles, and take the position that Acts is not always reliable. I. Howard Marshall (Witness to the Gospel, page 6) says it could be argued that Luke's account of the early church does not accurately mirror reality, even that Luke (or his sources) was presenting a picture of the early church that validated his own theology, going on to say that (if so) this would have been a deliberate procedure. Regardless of the conclusions Marshall reaches, Acts contains subtle comparisons between Paul and the apostle Peter and, for some reason, the author may have wished to make Paul a lesser character than Peter in the early church. A parallel that his early Christian readers might have noticed, between Paul and Saulus, would serve that purpose.
In conclusion, the one reference in Acts does not lead to a clear conclusion that Paul changed his name in Cyprus or at any time as a Christian. Paul never mentions the name Saul in his own epistles, even when it would have been reasonable for him to have done so, and we can find no reason for him to abandon a Jewish birth name, in fact to have done so would have offended the Jews he may have wished to convert. It is therefore possible, but not provable, that Paul was not at any time known as Saul, except in Acts of the Apostles.