The story appears in Butler's Lives of Saints, a standard reference for many saints' histories. The relevant part of the (brief) Butler's entry reads:
St. Gregory the Great tells us that when the Vandals of Africa had made a descent on Campania, Paulinus spent all he had in relieving the distress of his people and redeeming them from slavery. At last there came a poor widow; her only son had been carried off by the son-in-law of the Vandal king. "Such as I have I give thee," said the Saint to her; "we will go to Africa, and I will give myself for your son." Having overborne her resistance, they went, and Paulinus was accepted in place of the widow's son, and employed as gardener. After a time the king found out, by divine interposition, that his son-in-law's slave was the great Bishop of Nola. He at once set him free, granting him also the freedom of all the townsmen of Nola who were in slavery.
Saint Gregory's relation of the story is in Greek; but the editors of the Patrologia Latina have kindly provided a Latin translation, which appears in Volume 77 of the Patrologia, in Chapter 1 of the third of the "Four Dialogues".
The Latin version of the story begins:
Cum saeventium Vandalorum tempore fuisset Italia in partibus Campaniae depopulata, multique essent de hac terra in Africanum regionem transducti, vir Domini Paulinus cuncta quae ad episcopii usum habere potuit captivis indigentibusque largitus est. Cumque iam nihil omnino superesset quod petentibus dare potuisset, quodam die vidua advenit, quae a regis Vandalorum genero suum filium in captivitate fuisse ductum perhibuit, atque a viro Dei eius pretium postulavit, si forte illius dominus hoc dignaretur accipere, et hunc concederet ad propria remeare.
Sed vir Domini magnopere petenti feminae quid dare potuisset inquirens, nihil apud se aliud nisi se invenit, petentique feminae respondit, dicens: Mulier, quod possim dare non habeo, sed memetipsum tolle, servum me iuris tui esse profitere, atque ut filium tuum recipias, me vice illius in servitium trade.
That is (my own translation):
When, in the time of the cruel Vandals, Italy was depopulated in the region of Campania [Nola is in Campania], and many people were carried away from this country into the regions of Africa, Paulinus, a man of God, offered up to the captives and the needy everything he had that was meant for the use of the bishopric. And even though there was nothing left over which he could give to those seeking [help], one day a widow came [to him], who indicated that her son had been taken into captivity by the son-in-law of the king of the Vandals; and requested this man of God [to offer] his ransom, if perhaps that lord would deign to accept it, and to allow this one [i.e. her son] to come back to his own.
But the man of God, questioning the lady seeking his help about what she might be able to give, found that she had nothing on her except herself; and he responded to the lady, saying: Woman, I do not have anything that I might be able to give; but take me, myself; say that I am your servant by law, and so that you can receive your son, exchange me for him in slavery.
The story is rather long, but it goes on by relating how the widow initially laughed, but was eventually won over by Paulinus' eloquence. When they went to see the king in Africa, Paulinus claimed that he was good at gardening; and because the king's son-in-law loved gardens, the king agreed to the exchange. After Paulinus had worked in the garden for quite some time, and gained the son-in-law's confidence, he told him to make sure that the kingdom was set in order, since the king would soon die. The son-in-law mentioned this to the king, who decided he wanted to talk to him. Gregory reports that as soon as the king saw him, he began to tremble, saying to his daughter that he had seen in a dream this man and others sitting in judgment over him, and having him whipped for what he had done to them.
The king constrained Paulinus to tell who he truly was (after Paulinus tried to avoid the question), and when the king discovered that he was a bishop, he was very afraid of possible divine consequences, and offered to send Paulinus back to his homeland with whatever gifts Paulinus wanted to ask for. Paulinus responded that the only gift the king could give him was the freedom of all the captives from the city of Nola. The king managed to get all of these captives in Africa gathered together, and sent home with Paulinus on ships loaded with grain.
Gregory then points out the parallel between Paulinus and Christ, who had also taken on the form of a slave so as to free many people from slavery. The existence of this parallel, in a book of dialogues with religious purposes, doesn't in itself indicate that the story is mere fable; but his narration does seem to be the only source we have for the story—Gregory doesn't indicate any source he himself is using. Wikipedia reports that the Vandals did not invade north Africa until 429, two years before Paulinus' death, and only began attacking the Italian peninsula after this time; so the story may not be factual.