O, a 252 HP / 4 Atk / 252 SpDef Careful Muk (414 HP / 247 Atk / 328 SpDef) can pretty easily deal with all versions of this Skymin. The most dangerous would be a Modest Specs version (a stretch already because I have a feeling Timid is going to be the popular one just to outspeed Modest ScarfTran and Azelf / Starmie).
Still, even a Modest Specs version is dealt with easily enough.
Muk is never 2HKOed by HP Ground, and can always 1HKO back with Gunk Shot.
Granted, Gunk Shot is only 70% accurate, but this is easily dealt with with smart playing. If HP Ground does that much damage, you know it is Specs and can switch to whatever to set up your strategy, and a Muk at 55% (with Leftovers recovery, though it could also run Zoom Lens and increase Gunk Shot to 84%) is not a terrible sacrifice for that knowledge.
Muk also takes Seed Flares like a champ (since I seriously doubt Shaymin will use HP Ground first due to the high risk associated with being locked into a Ground move).
Seed Flare does a maximum of 129 damage to it the first time, and a maximum of 258 damage to it if it gets the -SpDef drop. Muk will always survive this with Leftovers, even with Stealth Rock down.
Muk basically gives you a 70% "counter" if Shaymin uses HP Ground. However, if it does, you are really at the advantage since you can set up your own strategy using that information.
If Shaymin uses Seed Flare, the only way Muk loses is if Seed Flare hits the first time and lowers Special Defense. Then Seed Flare hits and Gunk Shot misses. And then Seed Flare hits again. That's a .85 * . 8 * .85 * . 3 * . 85 = 14.7% percent chance. Meaning if Specs Shaymin uses Seed Flare, Muk is a "counter" 85% of the time.
Now, if Specs Shaymin decides to run Psychic (I dunno here it might be common it might not be), then Muk has issues. Muk can only not be 2HKOed with Leftovers against Timid Specs Shaymin, and that is only slightly above average, so if you get unlucky, it will be 2HKOed.
Of course, this is also assuming that Shaymin is at 100% health. If it isn't (and something simple like Stealth Rock is down and Shaymin is at 75%), Muk can just use Poison Jab and be a 100% "counter."
Even with Muk's slight concern with Specs Psychic, I think it can effectively deal with Shaymin since only the Specs Version is a concern. I've also always thought that "countering" Choice Pokemon isn't about establishing a perfect paper counter, since with Choice Pokemon you almost always play around them with many members on your team. Muk is basically one candidate to be a perfect "scout" to gather information on Shaymin.
If it is Specs, deal with it accordingly (switch in DD Tar (psychic / air slash), switch in DD Gyara / Mence / Nite (HP Ground), switch in Crobat or stay in (Seed Flare)). If it is anything else...beat it.
Go Muk!