my mom made a paleo sausage stuffing last year that was amazing. I know there was celery, sausage and other stuff involved... I'll see if I can get a better idea from her and post. It was way better than bread based stuffing.
eta- I'd try this + sausage http://www.marksdailyapple.com/bread...room-stuffing/
Google paleo stuffing there are quite a few ideas floating around out there.