Combat only happens when there are two opposing sides that want to attack each other. If you are unaware of any enemies, and your enemies are unaware of you, then no combat can take place. There is no grand universal transformation where time is suddenly divided up into 6 second intervals when someone decides to throw a punch. In your specific situation, you killed all your enemies, meaning there was no one actively opposing you. You were out of combat. If your paladin hadn't used Divine Sense to locate more enemies, you would both have been unaware of each other and not initiated another combat.

Initiative does not define combat. It is only there to keep manage the actions characters take. One round is about 6 seconds and all turns happen nearly simultaneously, but to make it possible to play in a reasonable way, an artificial order to actions is used to fairly allow all characters to perform their actions. Initiative can be used in circumstances outside of combat. Initiative does not have to be used to track combat. Like I stated above, the universe doesn't divide itself into 6 second increments when someone starts fighting. It is just a way to simulate a lot of actions happening all at once.

That being said, when are you allowed to short rest? According to the rules, you can short rest any time you have at least an hour to rest and do minimal activity. If you can relax for 600 rounds during combat, you can short rest. More specific to your situation, once you defeated your original enemies, if your DM didn't attack you with the wraith and banshees, you could have rested right then.