Как создать массив в массиве

Да, вы очень близки к вашей попытке с помощью Regex.Replace; последний шаг - изменить constant "wibble" на lambda match => how_to_replace_the_match:

  var text = "Once upon a time there was a %s0 and it was %s1";

  // Once upon a time there was a nathan and it was bob
  var result = Regex.Replace(
    text, 
   "%s([0-9]+)", 
    match => Globals.Words[int.Parse(match.Groups[1].Value)]);

Изменить: в случае, если вы не хотите работать с захватом групп по их номерам , вы можете назвать их явно :

  // Once upon a time there was a nathan and it was bob
  var result = Regex.Replace(
    text, 
   "%s(?<number>[0-9]+)", 
    match => Globals.Words[int.Parse(match.Groups["number"].Value)]);