他にもいい方法があるかもしれませんが、
Regex.Replaceの以下のURLのオーバーロードを用いて実現できます。
http://msdn.microsoft.com/ja-jp/library/ht1sxswy.aspx

' コード例
Imports System
Imports System.Text.RegularExpressions

Module Program
    Sub Main
        Dim text As String = "When I was a child, I went there."
        Dim pattern As String = "\w+"
        Console.WriteLine(Regex.Replace(text, pattern, AddressOf MyMatchEvaluator))
        
        Console.Read()
    End Sub

    Public Function MyMatchEvaluator(ByVal  match As Match) As String
        Return match.Value.Substring(0, 1) & new String("●"c, match.Length-1)
    End Function
End Module