I played a game today where there was only 3 cards in the encounter deck before the combat phase. I had all 3 Trolls engaged to me and when I dealt them their shadow cards it left the encounter deck empty. So did I instantly win the quest or do I need to resolve all of their attacks first?

I had enough allies to block with however one of the shawdow cards shuffled itself back into the encounter deck.

You won!

The forced effect on Stage 2B triggers immediately whenever either of the specified conditions are met. If that happens while assigning shadow cards, you advance to the third quest stage before resolving attacks.