Simple, what do each of these items want
What does the fire want? To consume
What does the water want? To flow
What does the wind want? To whisper?
What does the earth want? To endure?
Fire: I'd introduce a small, but very hungry fire spirit. It's been trapped in a library of tasty books. It can forever see what it desires, the tasty books, but can never reach them. Worse, the users of the library endlessly taunt it by bringing the books close to the flame so they can read it, but not close enough for it to consume them. How many valuable books will the party feed to the fire to gain it's blessing? Will the users of the library want their valuable collection burned?
Water: What if the water has been turned into a prison of ice. It holds something the party would rather keep trapped. It longs to flow again, to rush over rock and sand, to crash upon the coast. To free it also means freeing whatever the ice is holding. Will the party free an innocent element and unleash a the trapped thing? Can they best the evil contained in the ice or find another way to contain it?
Wind: The wind wants to whisper ideas to men. This wind wants to whisper some dangerous idea though. It might be the truth about the gods, the name of an ancient evil, seven words that would drive any man insane, or well, you get the idea. That idea is written on a piece of paper, a player only need to speak the idea to the wind. Will they unleash an evil truth to gain the wind's blessing? Can they supply a happier idea that wind will take instead?
Earth: The earth wants to build an enduring wall. This wall will seperate to rivals who always argue and fight. If they could talk, they might become fast friends. If they are seperated, they are sure to become enemies. One will always want what the other has on the other side of the wall. Will the party make new enemies to appease the earth, or can they talk the earth into building something enduring that doesn't cause strife.