It's poetic and archaic and mainly present in fixed expressions like the one above or in older things like the German version of the Lord's Prayer ("Dein Wille geschehe, wie im Himmel, so auf Erden"). But it's not used in normal speech or writing. You should be able to write "ein Paradies auf der Erde" instead. "Auf Erde" would be grammatically wrong though as you need an article here in German.
For the form, please see the comment thread started by Februar2014.
For the case: auf is one of a list of pronouns that can take either the dative or accusative case; when used to describe a location, they take the dative case. (The accusative case is for destination of movement.)
1 Thessalonians 5:1-11
 But of the times and the seasons, brethren, ye have no need that I write unto you.
 For yourselves know perfectly that the day of the Lord so cometh as a thief in the night.
 For when they shall say, Peace and safety; then sudden destruction cometh upon them, as travail upon a woman with child; and they shall not escape.
 But ye, brethren, are not in darkness, that that day should overtake you as a thief.
 Ye are all the children of light, and the children of the day: we are not of the night, nor of darkness.
 Therefore let us not sleep, as do others; but let us watch and be sober.
 For they that sleep sleep in the night; and they that be drunken are drunken in the night.
 But let us, who are of the day, be sober, putting on the breastplate of faith and love; and for an helmet, the hope of salvation.
 For God hath not appointed us to wrath, but to obtain salvation by our Lord Jesus Christ,
 Who died for us, that, whether we wake or sleep, we should live together with him.
 Wherefore comfort yourselves together, and edify one another, even as also ye do.