Leveling pets up until 20 requires, at most, winning three 3-opponent (L23-L25) battles per level without buffs (far fewer if you are leveling up using trainers). Every level after that requires a fraction more experience than the last. Assuming all pets are equal in a given discussion, L25, L24, and L23 (in that order) gain the most return for the stones being used to a player with a suitable stable of higher level pets. Any stone used after level 17 is 2-5 less battles required to level that pet (increasing as the level number gets higher).
A new battler, just starting out, however, might find better use for the same stones by leveling a "power pet" as quickly as possible, or getting a few pets to L5 to get a better start on the "core team". Once you have a core team that you can use to capture wild pets reliably, the first statement reasserts itself.
Using the upgrade stones only matters if the affected pet is actively being used to battle. Upgrades in rarity just increase battle stats, so if that particular pet is not being used to actively battle, then having improved stats is meaningless outside of the odd rarity achievements.
I think most battlers (myself included) prioritize using rarity stones on pets that are a pain to acquire or are not available in "blue" rarity to begin with. Once you start building a surplus of upgrade stones via dailies (or menagerie), then you go back and start stoning the ones you are too lazy to hunt for in the field. Otherwise, you just hunt for "upgrade rares" while waiting for raids to start or between quest hubs.