Four move King capture Black winning:
http://brainking.com/game/ArchivedGame?g=425688

Three move King Capture with Black winning:
http://brainking.com/game/ArchivedGame?g=325044

72 move King capture White winning:
http://brainking.com/game/ArchivedGame?g=250097

Actually capturing the King requires a turn to do so the two quick games listed are probably the fastest games you could play. Atomic Chess might have a faster game possible, I'll have to think about it unless someone knows already. Seems like three moves would be it in that game too.

You have me curious what the average length of games is. Backgammon is a fairly constant 18 to 30 moves. Dark Chess has quite an extreme range, but I'd guess the average for games played until the King is actually captured to be about 25 moves. I suppose I could just add up my wins and losses moves per game and figure an average that way. The number on the profile isn't always the right number though and you'd have to look for games that end in resignations. Or maybe not, since resigning is part of the game it could be part of a complete average.