In parallel to solving this puzzle, also does all the miners on the
blockchain compute the output of the deployed transactions into them?
Yes. But... When attempting to mine a new block, each miner can put whatever transactions they like into that block, as long as the output is valid. Generally the vanilla mining/client implementations prioritise transactions with a higher gas price, but miners don't have to follow this.
(See: What is the default ordering of transactions during mining, in e.g. geth?)
So each miner, working away on solving PoW, might be working on a block that contains completely different (though valid) transactions.
or when the winners are decided, will only the winners compute the
deployed transactions and generate their outputs?
The winner's block is accepted by the rest of the miners, who then confirm that the state changes performed by the transactions in the winner's block are valid.