I believe (and I may have some of the details wrong) Mark Sapir had at one time a curriculum for fourth graders that involved combinatorics on infinite words.  I do not know if he still has it, or how adaptable it is, but it introduced the Thue-Morse sequence and (I believe) had some applications, such as (non-FIDE) unending chess, analysis of certain dynamical systems, and so on.  Since I may be mistaken as to the details and availability, I suggest asking Mark Sapir or rolling your own.

Gerhard "Ask Me About System Design" Paseman, 2011.12.21