Та же идея, что и у полищука, но немного менее многословно
var res = Regex.Replace(input, ".+", "#$0#");
Поскольку регулярные выражения по умолчанию жадные, .+
будет захватывать всю строку. $0
захватывает все совпадение, поэтому нет смысла использовать явный захват в этом случае.