I would recommend the game SpaceChem. It is outstandingly parallel to programming in the sense there is branching, testing, looping logic and similar. You'll probably even love the game yourself. It has great commanding/minion play and a good story if they are a capable reader (the first being the first approach to teach boys, the second girls if you follow teaching advice for typical kids)
Minecraft does have a bunch of programming mods. Often times letting you make minions to do stuff for you (some cases in python or a custom language).
You could also consider starting with electricity. I've been through college classes for both programming and electricity. And the success of actually learning to read/make/trouble shoot electrical diagrams is much higher than it is for programming.