I'd want it that this only applies to pets that are actively following you. There's many circumstances where you might want to intentionally leave a pet behind.
No need to have this actually run turns on the level above. Just have it work out how many turns it would take to get the pet from its location to the stairs, then have it appear on the next level that many turns later. If it can't find a route (there's a river, say), then just stay where it is.
Could maybe apply to monsters too...