You could also try "Heidi" later - it's a classic story that should be easy to find. At a Berlin bookstore I even saw an easy reader using a vocabulary of less than 500 German words.
Some things I loved as a kid (sorry, can't remember what I read or watched when I was 4...):
- "Es war einmal..." : there are different TV programs published with this concept, for example "Es war einmal das Leben" (about biology), "Es war einmal der Mensch" (about history), "Es war einmal Amerika" (about American history), "Es war einmal der Weltraum" (about space)... Basically, these programs are very educational, but they use characters and stories that make e. g. a fever feel like an adventure.
- Augsburger Puppenkiste, they play different stories using string puppets, which are then broadcast on TV. Michael Ende (author of the "Neverending Story") wrote some of the underlying stories. See a sample of "Jim Knopf" at
http://www.youtube.com/watch?v=tPpqYAYgKK4 for example. Parents love their series because they are good quality programing and free of violence.
- Michael Ende books: it's a short way from the TV episodes to reading more of his works.
- (for older kids and youths) Karl May books: Karl May would be considered a classic author if his goal hadn't been to simply entertain people - the saying is "Goethe kennt man, Karl May hat man gelesen" (as a German you know Goethe, (but) you read Karl May). Last time I looked, there were 5 Karl May books in every German household, statistically. The stories are mostly set in either the Old West or the Orient, and they are the main reason why Germans are fascinated with Native Americans - there are a lot of clubs focusing on Native American culture here for example, while the number of Germans with Native American heritage is close to zero. Karl May portrays them as generally very noble and peaceful people - his books contain about as little violence as you could possibly have in a Western - and his books are said to instill values like truth, goodness and honor in the young audience. In the 60s there have also been movies based on Karl May's books, which still attracted enough TV viewers at their 54th repetition this year, but the movies are very very very loose interpretations of the books.