I run Saturday Kids, a digital literacy school for kids. We teach kids as young as six Scratch, a visual programming language developed by MIT Media Lab. I sent my 5 year old boy Camper to a couple of our Scratch classes. He understands the logic, but because he cannot read he doesn't know which blocks to use. Camper loves LightBot Jr though. It's a coding puzzle app that teaches kids how to command a robot. No reading required, so relatively easy for younger kids to pick up. If you are concerned about screen time you can try Kibo and Bee Bot. https://itunes.apple.com/us/app/lightbot-jr-coding-puzzles/id858640629?mt=8 http://kinderlabrobotics.com/kibo/ https://www.bee-bot.us/
IMO, it depends on what you want your kid to become. If it intends towards becoming a programmer or on a similar path, then you can start as early as 8-9 years of age. Before that, focus on their math and calculation skills. You can opt for some abacus classes. The more smart your kid is mentally, the faster can he/she grab things. But if that's not the case, then avoid providing computer usage atleast until 7th-8th grade. Computers/mobiles are addictive and keeps kids away from real touch of life, friends and families.
I personally think it will be about 5-6 years old when at least they can understand what is it all about and span of interest will be longer. There are kids younger than that taking up coding nowadays. You can try on their trial lesson to see your kids will love it or not.
To me, primary school level, Primary 1 will be great to start coding. This is because they can understand instructions and able to read well too. You can check out Discovering Without Borders Facebook group to find out more.