Help me out here with a ruling...

K is free kicking from their 40. The ball was placed on a Ttee and as the kicker runs to the ball and is within one step, the ball rolls forward off the tee. The kicker continued and kicked the ball.

I kill the play as soon as the ball falls off the tee.

When the ball fell off of the tee L should have been blowing it dead. Even if K was about to kick it when it blew off. The clock doesn't start right away so blowing it dead even after it is kicked is not a problem. Get that blown dead as soon as possible and just line them up again.

I'm just too quick, Warren! :)

Why are we killing the play? The kicker made no effort to stop. I understand the wind thing. But in those cases the kicker will stop and not kick the ball. In this case the ball falling from the tee and the kick were nearly simultaneous.

Preventive officiating
 

The same reason I yell "Mouth pieces and chinstraps! or "Back up Blue!" to the WR who runs out to line up and intially stops beyond the ball. Preventive officiating.

I kill the play because he can't legally kick the ball from where it now lays. K shouldn't be penalized for delay of game because the ball fell off the tee, so we're going to kill the play anyway and give them another opportunity to set up. Why wait until after he kicks the ball?

If the ball is ready for play and suddenly starts rolling toward the sideline, are you going to let the sanpper run over and snap it? No, you're going to kill the play because the ball has moved from it's original spot.

Why are we killing the play?

Since K is free kicking from their own 40, can we assume that this is a kickoff?

It was not a drop-kick. So ...

... the ball must be kicked from a fixed position;
... the ball must be kicked from a designated spot;
... the ball must be kicked from the free-kick line;

When the ball fell off the tee, the above conditions could not be met. The ball cannot be legally kicked, therefore the play cannot start. Blow it dead.

I even have a cable modem. :D

In your original post, you said the ball fell off the tee when the kicker was one step away, and here you say nearly simultaneous with the kick. It can't be both.

I doubt the kicker would even notice the ball falling away if it were truly simultaneous. The point being he probably could not stop if it were that close, therefore if you see starting to fall, you kill it for the reaons the others have pointed out.
It's one of those talked about mechanics that I really have not seen in formal print that the official covering the kickoff will do.