Is it possible that two miners mine blocks with different headers because they include different transactions Ok, it's a yes or no question: miners can include different transactions in a block, so does that mean that they search for different nonces
Yes, different miners will almost certainly always search for different nonces. Besides including different transactions from the network, they will also almost certainly send the proceeds from the coinbase transaction to different accounts. There are many other places where the block can also be different.