Now my daughter is five and plays with Scratch Jr. She makes short clips of characters moving around, recording and timing the characters voices, allowing presents and balloons to magically appear, she's not tying in code but instead uses "graphical programming blocks". She also likes codeSpark.
My kids do not distinguish programming from play. I intend to keep up programming = play which I will later transition to a more advanced version of, "I want to make a thing, writing a program will allow me make it." than what my daughter is currently doing. Make it fun, and don't do much in the way of suggestions/feedback, just let them know you'll answer any questions and let them make mistakes.