My DS9 entered a small, private kindergarten at 4 1/2 and did great, but he's always been very comfortable in the world and in his own skin, which made things easy. I've always been able to drop him into new situations, like a summer camp he's never been to with kids and teachers he doesn't know, and not only is he eager to go, but by the end of the week, he's made new friends. As someone who suffered from crippling social anxiety as a kid, I am constantly amazed by this.
I would suggest having your son visit the kindergarten for a day or two and see how he reacts. My son visited for an entire day when he was 3 1/2 and came home super excited.
For us, starting kindergarten early also meant fewer skips and less disruption later on. DS did later move up from 4th to 5th, which drew some attention, but few people knew or realized then that that was actually his second "skip," since the first one was built in up front.
