Can I use Rare Candy on a Pokémon that was devolved on that same turn (i.e. Devolution Spray, Hyper Devolution Spray, etc.)?
No, you cannot. A Pokemon must be in play since the beginning of the turn in which you are using Rare Candy. A devolved Pokemon counts as just coming into play.
Source:
PUI Rules Team (2004-06-03), PUI Rules Team (2004-06-09)
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.
What does "This counts as evolving that Pokémon" mean, in game terms?
It counts towards the one evolution per turn for that Pokémon (with exceptions for Trainers and Pokémon Powers that break that rule) and removes Special Conditions on that Pokémon.