ZZT is how I got my start. It is a very old game and of course the "graphics" are terrible, but the game is solid and it's fun. Once you get a little way in you'll come across levels such as The Bank. The Bank is an amazing room (for a ten year old) and for me the concept of programming soon clicked from that experience. In The Bank, you see how you can combine pushers, blocks, and sliders to create a really cool combo lock mechanism. Then, as I recall, there is a little character with some basic programming.
Anyway, the neat part of ZZT is the editor. You can make your own rooms and as you build your own rooms, you are effectively programming. From simple things like placing monsters and choosing types of breakable walls, to creating physical machines using pushers and sliders, and, finally, to programming using the ZZT object scripting language which allows you to create objects that react to events (e.g. 'touch', 'shot', 'timer', etc.) with actions (e.g. 'print message, aka talk', 'move', 'shoot', etc.).
ZZT is the game that did it for me. After a little time there I was moving on up to Turbo Pascal and QBasic. I don't know what contemporary kids would think of ZZT today, but I would think you might be able to convince them to give it a shot.
ZZT is freely available to download and still has a small dedicated fan group following online.