Can you use Rare Candy to evolve a Mysterious Fossil into an Omastar or Kabutops, or use it on a Root/Claw Fossil to evolve into Cradily/Armaldo?
It can. It counts as a basic Pokémon while in play. Omastar, Kabutops, Cradily, and Armaldo are Stage 2 Pokémon; you could use Rare Candy on the Fossil trainer to skip to them.
Source: PUI Rules Team (2003-10-16)

Relevant cards

Note: All applicable cards may not be listed below.
BW10_105
BW10_85
BW5_100
DP4_102
EX13_90
EX2_88
EX9_83
HGSS2_82
POP5_7
POP8_10
SM1_129
SM2_165
SM7_142
SWSH1_180
SWSH1_180
XY5_135