Stella Mare, as Joe says, or Stella Maris would seem to be correct- unless Stella Maria is dialectical. The 'Maria' is not needed for rhyme, so ?

"Sägen es war einmal" is an idiom; Joe has about as good a translation as possible.
My dictionaries have many 'sägen....' idioms, a column in Cassell and as many in Langenscheit and there are probably many more.

Very interesting tune- I couldn't come up with a composer that I was sure of.