What things did you think were important to learn, what kinds of things motivated you most? What did you do when you got stuck?
So what helped me most was just experimenting a lot, banging my head against a wall repeatedly. When I got stuck I just had to keep trying. Knowing I could Google problems was really helpful, but I also had to learn how to Google. I was motivated by the amazing feeling of finishing something I built, and also the fun of learning and then applying that knowledge.
It's hard to remember my tiny self so I wish I could give better advice. I most of all wish that I had a mentor figure, someone I could ask for questions or who could show me where to look, or even just be a role model. Getting into open source and talking to people online was amazing, although I didn't start that until I was ~12.
It took me a really long time to get where I am. There are probably more efficient ways to do so other than banging my head against things. But it does work! So just encourage them to keep going, and MOST IMPORTANTLY, FOLLOW THEIR INTERESTS!
If they can create/combine algorithms to solve a problem... that's most of programming.
I'd start with the "robot" problem: have them write a set of steps to complete a simple task, and then have them (or better, someone else) go through the steps precisely (no cheating and assuming they meant something they didn't write!). Then iterate and add/remove steps until the task is actually doable. (Disclaimer: idea cribbed from someone else)
That gets them to grok the "everything needs to be in a program, and a program is only everything that's in it" idea.
The traveling salesman problem (recast in whatever form would be most interesting to the kids) and graph theory problems are also especially visual and explorable.
To date myself, for me it was the computer game The Incredible Machine, which was a Rube Goldberg physics puzzle game... in 1993 on DOS. ;)
Critically, the failure-iteration loop was tight, which really impressed "if at first you don't succeed, try try again" on my younger self.