Ok, now we’re cooking with gas! They cite The Sharks of North America (Castro, 2011) which says:

The name “nurse” comes from “nusse,” meaning fish, which appears in print as early as 1440 in the Promptorium Parvulorum, an early English/Latin dictionary. […] “Nuses were there so plentie, that they would scarcely suffer any other fish to come neere the hookes” (Hakluyt 1589).

According to the Oxford English Dictionary, “nusse” is derived from the earlier “huss,” the ancient name for the catsharks

The Promptorium Parvulorum has an entry for husk:

Husk of fyshe: Squamus, -i; Masc.,

with a note against that entry:

‘Huske, fyshe,’ Harl, some kind of fish.

• ‘Hush, the Lump, a fish,’ JAMIESON.
• ‘Husse, a fysshe : rousette,’ PALSGRAVE.
• ‘Huss, the dogfish,’ HALLIWELL.

So we have to trust the OED about the transformation from huss to nuss. I guess it could be the classic misdivision/rebracketing (“an huss” becoming “a nuss”) that gives us “nickname” and “newt”.