For sure it starts with K. Pronounced Ko lo jay. There is a d on last syllable is similar to dij.
If polish spelling rules are applied to "Ko lo jay" it'd look like Kolodżej.
However, Kołodziej is more likely to be your answer as it is a real polish family name but it is NOT pronuced "Ko lo". But instead "Ko wo" with a soft ł, similar to the "W" in "Washington".