For the purposes of this post I divide moves into three categories depending on their relevance to the design. The moves I deem make sense on a given Pokemon are marked Plausible. Such examples include Earthquake Whiscash, Petal Dance Roselia, Hi-Jump Kick Hitmonlee, Heal Bell Chimecho and so on. The moves that stretch the implications of the design are marked Possible. Calm Mind Corsola and Focus Punch Furret are two examples. The moves that make little sense on a given Pokemon are marked Unlikely. Examples would be Rapid Spin Hitmonchan and Explosion Corsola.
The idea behind this is that our Pokemon's movepool would "make sense" if we chose from the "plausible" and "possible" pools.
There are also conditional moves - moves that would make sense only if a certain body part is included in the design. Those will also be listed.
I am mainly choosing from the utility pool of Gravity, Rapid Spin, Wish, non Dark weak Trick Room, OU viable Heal Bell / Aromatherapy, Encore, Memento, Non Dark weak Perish Song, Psycho Shift, Safeguard, Magic Coat, Me First, Snatch, Spikes, Toxic Spikes, Tailwind, Mean Look, Block and Haze, as was quoted in the opening post, but adding a few attacking and support options (Especially since we want this thing to be able to sufficiently scare off Garchomp), as well as some useful traits. Feel free to suggest additions to the "utility pool".
Mongolian Deathworm
Plausible: Thunder Wave (Some Electric moves in general), Magic Coat, Snatch, Haze, Knock Off, Block, Spikes, Toxic Spikes, Crunch and elemental Fang moves, most notably Ice Fang. The last four require spiky teeth, radula or a similar equilavent.
Possible: Gravity, Me First, Reflect, Light Screen and Encore. Encore requires some stubby feet similar to those found in velvet worms. Perhaps we can also add their retractable claws for a rather nice look.
Unlikely: Wish, Heal Bell, Memento, Perish Song, Rapid Spin, Tailwind, any form of Sleep move, Ice Beam, Thick Fat trait, Levitate trait.
Catoblepas
Plausible: Hypnosis, Haze, Perish Song, Heal Block, Gravity, Haze, Block, Mean Look, Thick Fat trait, elemental Fangs, Head Smash (!!!) We probably don't want to give this thing both Block/Mean Look and Perish Song, keep that in mind. Chaosbreon + Substitute/Perish Song Catoblepas may see use, though, if it ends up being fast. Head Smash seems decent on this guy, considering he also gets a good Earthquake, and it makes sense as the Catoblepas has a head so heavy it can only stare down - it using that head as a bludgeon isn't that far off.
Possible: Ice Beam, Snatch, Memento, Thunder Wave, Magic Coat, Me First, Knock Off.
Unlikely: Wish, Heal Bell, Tailwind, Spikes, Toxic Spikes, Rapid Spin, Levitate trait.
Thorny Devil
Plausible: Spikes, Toxic Spikes, Safeguard, Gravity, Block, Haze and elemental Fangs.
Possible: Me First, Snatch, Trick Room, Rapid Spin, Reflect, Tailwind, Knock Off and certain Dragon moves. Tailwind needs a particularly fitting design, as it is hard to design a Poison/Ground with it. Knock Off probably requires a large tail.
Unlikely: Wish, Heal Bell, Trick Room, Memento, Perish Song, Ice Beam, Sleep moves, Levitate, Thick Fat.
Keep in mind this list is rather subjective, and feel free to correct me. I currently hold the deathworm in high favor, as I really like Pokemon based on mythological creatures.