I have continuous problems with attenuation and I'm looking at starter sizes and mash temps to resolve it. How big was your starter? In my opinion a Kolsch needs to be fermented at a very low ale temp, that being said, you need at least a 1 gallon starter for the yeast to eat all those sugars and with a 90% pils malt in your bill, you are likely going to get a load of fermentable sugars rather than a bunch of non-fermentable dextrins - so I'm guessing, even though you made a starter, it wasn't big enough - did you use a stir plate? did you check manufacture date of your yeast? I had the exact same problem as you w/the Kolsch I did a few months ago.
Here's a case I had with my last batch:
Brewed a 10gal Brown Porter OG 1.060
5 gallons on top of a carboy of ESB yeast from which I just racked off a standard ordinary bitter: it started fermenting the minute the wort hit the yeast, and took one week to make a nice dry 1.008 (I think, though could've been lower) - anyway it fermented all the fermentable sugars and left some pleasant sweet dextrins.
Other 5 gallons on a 1/2 gallon starter of London Ale Yeast (the stuff that's supposed to ferment out pretty well): ended in 3 weeks w/a 1.020 FG....tasty, and actually closer to a brown porter, but too sweet for me.
Moral of the story: I pitched my wort on a giant active yeast cake and it fermented fully, whereas the 1/2 gallon starter just didn't cut the muster....