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. Just by listening to these, the vast majority are major 80%+, followed by minor, other modes apart from minor probably make up less than 5%.
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. Some notes are repeated. and most combs are tuned specifically to a song. so 'london bridge' will have a different comb than 'this old man'. You can see a video on this here. And here's more technical info 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".
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:
- Invert chords to make them fit.
- 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).
- 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, the dots aren't completely aligned.
Also, if you want to hear what it sounds like, search for "music box maker". they go for under 20 bucks, and let you punch custom holes on paper that you crank out through a music box.