Right off the top of my head [& I'm not a foley artist, so you'd have to work out the details]
sharp points to feet - high transients
lots of legs - 'skittering'
rhythmic walk - pattern that could become 'signature'...
& don't forget ...big, so lots of things dropped an octave, added subs
'skin' movement noises, not synced to ...
No one sound is going to do this, to get this right your effect is going to need to be a composite of several different layers. Your celery idea might form part of one layer, but is never going to do the whole job.
I'd be thinking:
Low ground rumble (sub)
I've found that most of the best sound designers for film and games start with real animals and insect vocals and layer and manipulate from there. Just to let you guys know,
I have a HUGE collection of unusual creature vocs that have been used on many many well known games and movies. And since they can be used in so many different combinations and ways of ...
Is it a swift or quick action or does it allow a lot of detail?
Is the soil dry or wet? Can you think of a character or emotion for the trees?
Have you tried some dirt sounds from your library or did you record some?
Divide the sound into at least 3 layers/concepts: low (wood resonances), mid (mud), high(celery) (freq) or mass, force, strain,...
If you realy want a monster use horse and other animals:
Pitch them down, use granular stuff on them, vocode them with other animal sounds.
Remove bottom end a bit if it gets to bass heavy on extream pitch shifts. at the end you cna alos use eq-notch sweeps or formant filters to give some more definition.
That could help if you want to make them growl.
Clearly from what Arnoud has said, you need to meet the character defined by your visuals. Having said that I'd be inclined to be fairly literal here and record the sound of you pulling some plants out of soil. If you can get the microphone in nice and close you should get a nice proximity effect that when boosted up should give you the impression of ...
I always liked the hipass tapping on desk, and i love making some weird insect like sounds with my mouth and pitching them up and stretching. I usually will try things like tongue clicking, fluttering, or (sorry to be gross) getting some liquidy noises.
I agree, I find those sorts of sounds challenging too. I've had some success with close micing my hands running over a few days worth of stubble on my chin. Gives a kind of creeping tentacle like sound. I read about that somewhere. Of course you have to watch your breathing.