A method which, given a string, returns a string in which each character is separated by an asterisk
Well, you've used recursion, but I wouldn't say that's a recursive solution because you have variables outside your functions that control what your functions do. 

A recursive solution will have a function that is repeatedly called with smaller and smaller sub-problems, terminating in a base case, that together will accomplish your goal. A key aspect of recursive solutions is that the recursive function returns a value - your method is void and so returns no value.

As a first step, discard your index variable entirely. At each recursive step, call BuildNewString with a smaller version of the same problem. Combine the results in such a way as to produce the desired result.