Thx to the steam forums I found the answer: You just need to DRAG AND DROP the Elemental staff onto the Lava fountain (forge) at the NE corner of the map. A fire elemental spawns and you receive a special rune which you have to USE in front of the prison.
Half of the "fun" in this game is googling, It's just ridiculous.
