Once I figured out a key concept, how and when to use Str and Add, I managed to pass it in C# without much trouble.
The fact the description mentions "Exp", though in some occasions more specifically requires "Str" doesn't help :s
However, the "core" example test shows how to use these classes. Let's say you have "abcd" (a sequence of 4 x normal). This should be treated as a fold of Add with the seed being the first list item wrapped with Str: Add(Add(Add(Str(a),b),c),d).

Good kata!
Still, I'd prefer to see example with -x and big numbers in initial unit tests.
For example:

Assert.AreEqual("-x+1", KataSolution.Expand("(-x+1)^1"));
Assert.AreEqual("y^15-75y^14+2625y^13-56875y^12+853125y^11-9384375y^10+78203125y^9-502734375y^8+2513671875y^7-9775390625y^6+29326171875y^5-66650390625y^4+111083984375y^3-128173828125y^2+91552734375y-30517578125", KataSolution.Expand("(y-5)^15"));                             

sorting is O(n * LOG(n))

Sorting the list just to find the element is doing O(Log(n)) complexity task where O(n) task is totally enough.