Add index to duplicate entry in List
If you collect the indices along with the duplicates, you don't need to loop over the list again:

var header = new List&lt;string&gt;();
var duplicates = header.Select((x, index) =&gt; new { x, index }).ToLookup(x =&gt; x.x, x =&gt; x.index);
foreach(var duplicate in duplicates.Where(x =&gt; x.Count() &gt; 1)) {
  var start = 1;
  foreach(var index in duplicate) {
    header[index] = $"{duplicate.Key}{start++}";
  }
}


This uses string interpolation ($-strings) as a shorthand for string.Format.



On premature optimisation:

You seem concerned about the \$O(n^2)\$ performance of your solution. At the same time you mention your actual input will have ~30 items. Before spending too much time worrying about the efficiency of your code, did you try to find out whether your current solution is problematic? It seems to me that the list is small enough that even a less efficient solution should be quick enough. 

Before trying to optimise specific parts of your code, ask yourself two things:


Do I need to optimise? Is execution time currently a problem?
Where is the efficiency problem in the code?


Before optimising, profile your program to figure out where the problems actually are. Before that, efficiencies like  \$O(n^2)\$  or \$O(n \log n)\$ are purely academic.