Hmm, according to the charts I have seen, M is generally end of 2nd grade, so it shouldn't be that hard to find some books to put in a kindergarten's bin. If they are being difficult about it, could you select some yourself from the school library to put in there? Or bring some from home. If you are looking for something at that level, most of the Magic Tree House books are M. My DS loved those!
I don't know why they get so difficulty about being able to "find" the right books for above average readers. It IS a school, for heaven's sakes. There are probably a few books lying around waiting to be read!

But I agree that if he's overall pretty happy and has the opportunity to read more challenging and interesting books at home, maybe it is not worth the battle. I agree with 2giftgirls, the teacher is not expecting him to talk about the story or characters much, she is teaching the rest of the class how to sound out simple words at this point. Although that is all the more reason to just give him books at his level, since she is basically not going to be teaching him much regarding reading.