Like someone mentioned logo or the old basics - if kids start in that environment they pick it up quite easy. They pick up concepts (wtf variables, yes does not matter how they are named, conditions, for cycle, functions) and there is instant gratification and little complexity. Just playing those games with little robot and arrows that "programs" it or simple scripting language in some game already makes much difference.
Then you can move on compiler and java or C - because basics are out of the way and it is the time to deal with what you call incidental complexity. Basically, one concept at a time. It is a bit as like teaching quadratic equations to people who were never taught normal ones nor much arithmetic.