In a 4p game, you should be more eager to take an early Province than in 3p or 2p. There are two reasons for this. First, in 4p each Province is a larger share of the available points, and you have on average a smaller number of turns. Second, in 4p you are more likely to see the game end on three piles before all the Provinces are gone. As a rule of thumb, I would grab the early province in 4p, but not in 3p or 2p.
That said, what are some of the Kingdom cards that would indicate that you should hurry or not hurry?
Tournament, as swbarnes2's answer indicates, is a very powerful card, and its presence means that Provinces in your deck are very important. In Tournament games, never pass up the opportunity to get a Province.
Explorer is another card that keys off of Province, but it's a fairly weak card, and you can't be sure of connecting it with a Province when you need to. I don't consider its presence a reason to hurry.
Cards that give you something else very strong to do with your money should make you think twice. Overbuy cards like a Masterpiece or Stonemason (with a good target) give you more than the usual opportunity to improve your deck quickly, and are likely a better choice than Province on turn 5. Goons, King's Court, and to a lesser extent Expand are other important cards can be very attractive for an early turn. Depending on what the other players are doing, other powerful $5 cards like Wharf, Cultist, or Rebuild might need to take priority.
By contrast, what would suggest that you need the Province right away? First and foremost, look for piles that might empty out. For instance, if Ironworks is available with attractive targets like Great Hall, Fishing Village, Ironmonger, Gardens, etc., those piles are likely to deplete very rapidly in a 4p game, and you should grab the points while you can!
By contrast again, look for cards that will slow the game down--an absence of buys, and delaying attacks like Militia or Ghost Ship. If those attacks are flying, you're going to have a lot of trouble buying a second Province without a good deck, so you're likely to want Gold. (Sometimes in a 4p game you don't need to bother with attacks yourself if everyone else is playing them for you!)