You may be asking “What on earth is a “pleonasm?”. Wikipedia warns you not to confuse a “pleonasm” with a “neoplasm” which is an abnormal and excessive growth. That would clearly be inappropriate. A “pleonasm” on the other hand is the use of superfluous words. For example “burning fire”, “free and gratis”, “each and every”. Sometimes pleonasms are used intentionally for literary effect.
Our village “North Arm Cove” was, of course, named after the adjacent waterway. That waterway has had several names over the years.
In 1826, the deputy manager of the AA Company, Henry Thomas Ebsworth, drew a map of Port Stephens that included many Aboriginal names. On this map, Ebsworth combined the Aboriginal name for the waterway: “Baromee”, with a descriptor of the type of waterway, the English word: “Cove”.

Wikipedia tells us that a cove is a small bay or coastal inlet - and that coves usually have narrow, restricted entrances, are often circular or oval, and are often situated within a larger bay. So “Baromee Cove” seems quite apt. (The local community once battled unsuccessfully to have the name of the village changed to Baromee.)
But in the same year, 1826, Ebsworth also drew a birds-eye map of the Port, this time with mostly European names. On this map “Baromee Cove” was replaced with “North Arm”. It seems Ebsworth was persuaded to combine a direction: “North” with a different descriptor of the waterway type: “Arm”. As a name, it’s not particularly original. There are lots of North Arms around the world including one near Murwillumbah. There are many west, south and east arms too.

Wikipedia says: “In geography, an arm is a narrow extension, inlet, or smaller reach, of water flowing out from a much larger body of water, such as an ocean, a sea, or a lake.”
In 1845, Phillip Parker King, surveyed Port Stephens and he appended the word Cove to North Arm to give the waterway its current name. He probably thought Cove was a better descriptor of what he saw.

But this expanded name includes two different (but overlapping) waterway types in succession – what I suspect is a pleonasm.
King’s addition did make the name unique. I haven’t found another placename with the words “arm” and “cove” together. Type arm cove into your browser of choice and see what comes up.
Over the years, North Arm Cove has been called other names. For example, to the fishermen of the 1940s and 1950s it was known as Bundabah Bay!

So, are we a cove, an arm or a bay?
Should the waterway be called North Arm Cove Bay?