Initially, I've tried to issue first K-1 unicolor guesses to determine counts, but it turns out it wasn't necessary. This approach gets no information about ordering from the first guesses, and I've got ~100 score from it (my second submission).
I did not participate in this match, but I thought of the first phase of finding the counts of colors:
First try k-1 guesses with 2 colors in each guess (half of one color, half of other, randomy sorted).
let`s call the numbers of pegs in each color A,B,C,D. Then (for 6 pegs) You have:
guess: ababba, result:1 miss,1 hit, equation: C+D=6-2
guess: ccacaa, result:1 miss,0 hit, equation: B+D=6-1
and last equation: A+B+C+D=6
Assuming that no peg color constitutes more than a half of the key, this will give the number of pegs and some information about placement in k guesses. But I guess the further part of telling which peg goes where was the difficult one :)