динамическое строковое форматирование с помощью string.format и Список <T>.Count ()

Самым простым способом, вероятно, является динамическое построение строки формата:

static List<string> FormatFileNames(List<string> files)
{
    int width = (files.Count+1).ToString("d").Length;

    string formatString = "Part_{0:D" + width + "}_{1}.pdf";

    List<string> result = new List<string>();

    for (int i=0; i < files.Count; i++)
    {
        result.Add(string.Format(formatString, i+1, files[i]));
    }
    return result;
}

Это можно сделать немного проще с помощью LINQ, если хотите:

static List<string> FormatFileNames(List<string> files)
{
    int width = (files.Count+1).ToString("d").Length;        
    string formatString = "Part_{0:D" + width + "}_{1}.pdf";

    return files.Select((file, index) => 
                            string.Format(formatString, index+1, file))
                .ToList();
}