Programming is not the backbone of primary education and you shouldn't design a education curriculum around a niche subject. Primary education is for teaching literacy, history, and arithmetic not a trade.

But you can certainly teach programming with pencil and paper. Some of the most influential programmers in history of computer science did not do their work on physical computers or used (now) esoteric methods like punch-cards as input. Several of my university CS classes were all pencil and paper, especially midterms and exams.