I think it's a spionid worm palp (basically feeding tentacle). I would expect to see multiple arms of a starfish in close proximity, especially if they were this long.
The coral is a little tougher, but my first thought is Turbinaria mesenterina, the large interspersed polyps are not common for Montipora sp. It looks a lot like the "LA Turbinaria" to me.