Further clarification:

Paradise probably does not refer to the contemporary town on the Avalon Peninsula, as described above. Paradise, Paradise Sound, Paradise River, Little Paradise and Great Paradise were all found on the west side of Placentia Bay. These are all abandoned. Since all other locales referred to in the song are on or near Placentia Bay, the reference to "Paradise" likely refers to one of these.