Keep it simple. I'm especially fond of music boxes. One of my main instruments is a celeste and I play hundreds of these types of songs. So this topic is near and dear to me.
Not sure why everyone's bringing up modes. The majority of music box songs are very simple and are usually in a major scale as music boxes generally depict traditional songs or upbeat songs for children (think "Somewhere Over the Rainbow", "Happy Birthday", etc). So your C major is fine. There's a big list of music box songs you can listen to. Play close attention to the 18 note and 22 note music boxes.
I analyzed the 354 music box songs of the 18 note movements in the link above. 310 were major (87%), 45 were minor (12.7%), 3 were modes and other scales (0.8%), 6 were mixed modes (1.69%). An example of a mixed mode song is "and I love her" by The Beatles.
So you see major is the most used if you want a traditional music box sound. That said, minor melodies and other modes can be very beautiful. One of the reasons why both Harry Potter and Sugar Plum Fairies have that "magical" feel to them is because they're minor on a celeste/bells instrument. Because people are mainly conditioned to hear major on bells (due to kids songs mainly), minor has a unique and mysterious tone to them.
Also worth to note that your typical 18 tine music box movement doesn't "waste" any notes. the comb doesn't have notes that don't appear in the song and more than likely it'll be diatonic. although it can have a non-diatonic tones in there if the song calls for it. Most combs are tuned specifically to a song. so "London Bridge" will have a different comb than "This Old Man", due to repeated notes. See here under "18 note movement information" see how it says "duplicate pitches (teeth) are necessary whenever a note plays again in less than about one second (which happens alot). Most movement combs have between 4 and 10 duplicated teeth, limiting the overall number of different pitches to about 14 or less". Also you can watch a video on this here.
In a music box, usually the melody is emphasized. So start off with the melody, then harmonize it afterwards.
In order to harmonize it properly you may or may not have enough room for full chords in two octaves:
1. Invert chords to make them fit.
2. Play a subset of the chord. So instead of playing 3 notes, you can play 1 note (root of the chord) or two notes (root+fifth,root+third, etc).
3. Try a different key. certain melodies/chords fit better in different keys for two octaves.
Another element of music boxes is to slightly arpeggiate a chord. This can happen on a cadence or when you want to emphasize a chord. But it's very quick, it provides a cute "jumbled" kind of sound. let's say I'm playing a C5 chord. so I'll play a C note, followed by G a few milliseconds afterwards, so they sound like they're together but not quite. you can also do this on full chords. You can see an example if you look at a music box, notice that on cadences and other chords that are emphasized, the dots aren't completely aligned.
Also, if you want to hear what it sounds like on an actual music box, search for "music box maker". they go for under 20 bucks, where you punch custom holes on paper and you crank out through a music box.