Check out LEGO Mindstorms, it's basically LEGO with motors that you program. I think something physical attached to the (abstract) programs would be a great way to start.
It's recommended for ages 10+, but I'm sure a bright kid with an adult helping would love it.