A great paleo substitute for quinoa is cauliflower rice, sweet potato rice, potato rice or other riced vegetables.