I keep thinking we need a sticky about successful tank decor. You should be keeping low lights so that is a consideration in addition to stinging and uprooting.
With the lower lighting (I only use LED's - 100 of them in 5 dome lights attached to a board) serpent stars (OK so it is not a coral) are more enjoyable than in other tanks because you will see more of them. They come in a variety of colors from red, to striped to yellow (common lore is to avoid green and I
know there are some agressive greens but I have one that is not but is of a different variety than the ones that get large).
Feather dusters will not harm the octo. The jury is out on whether or not the reverse is true. My pencil urchins ate my feathers - as well as a non-photosynthetic gorgonian - when there was not enough algae (imagine that) in the tank to sustain them (I now add sea panseys every couple of months but did not add new feathers). Nancy has read reports that some octos will decide to decorate with the feathers causing their demise.
Red mushrooms work well in the low light (they won't get huge like the one in my reef tank but they will live a very long time) but will look more brown than red. My dwarf never bothered the couple I have in there.
There is a nonphotosynthetic sponge that is a light bright orange (Ken calls them frilly sponges but I don't have their proper name at my finger tips. Check with Dan or try
www.sealifeinc.net to look them up.) These are the only sponges I have ever been able to keep for a long time and they seem indestructable unless they start getting covered with algae.
For additional color, you can try the purple and white barnical shells. These do well in the aquarium and may serve as a den for the octo. Be sure that anything dead you buy has not been treated or coated to "preserve" it. Clorox treatments are ok as long as it has been declored for at least 3 weeks (you may want to do this with anything purchased dead to be safe. Anything picked up on the beach you should consider a 2 week clorox bath followed by 3 weeks of declorination - old school SW tanks
).