Mining Process - Transactions Selection
Most miners today simply use sort transactions by fee/byte and include them in blocks. This is optimal strategy for revenue maximization(ignoring the knapsack errors).

When the nonce space is exhausted, miners can either change the timestamp of the header or they can use the additional space in the first transaction(called coinbase) where they can put random data. Changing this random data changes the merkle root, on which you try out 2^32 nonces.

So, to answer your question miners don't necessarily try to find new transactions that will find the solution, they can mine the same set of transactions with a little change in first transaction that does not affect the outputs any transactions in the block.