The 2008 OED lists 'octopuses', 'octopi' and 'octopodes' in that order; with use of the last indicated as "rare".

If you want to use the correct Latin name for the creature, then it's polypus (singular) polypodes (plural).

IIRC, 'referendum' is a Latin gerund, so has no plural.

'Referenda' - meaning things to be referred, and necessarily connoting a plurality of issues - is the Latin plural gerundive.

As to octopi, they have six arms and two legs.