I like Tom's of Maine natural tooth products,
although the toothpaste contains a coconut oil
derivative (but isn't this OK by

most paleodiets?).  Tom's tooth products contain
no sweeteners yet has a pleasant taste.
When I worked in South America, the rural health
workers taught people to clean their teeth by chewing the end of a stik until

it was soft, then just scrubbing the teeth with
this "brush".  I learned from them that toothpaste isn't really necessary;

what is important is to remove food particles by
brushing.  I also learned from my children's dentist recently that most of

the recent research shows that flouride doesn't
do much either.  What causes tooth decay is residual starch and sugar on the

surface of the teeth, which feeds
bacteria.  People who consume excess starch and
sugar have their work cut out for them in

keeping their teeth clean enough to keep the
bacteria at bay.  Case in point -- my mom recently took a group of dentists to

treat children in Eastern European orphanages who
had terrible dental problems, brought on, the dentists reported, by a diet

based mostly on potatoes.  Also, hunter-gatherer
tribes tend to have few or no dental problems, until they begin to tr
  ade with outsiders for bread and candy.  And on
a paleodiet, you aren't consuming all that stuff.
Plain old baking soda is a good "tooth powder" to
brush with; old fashioned "tooth powder" was calcium carbonate (chalk) and I

think it is still sold in some drug
stores.  These both act as a gentle abrasive to
help remove the "fuzz" from your teeth.

You can also use hydrogen peroxide as a rinse,
or, if you search the internet, there are a few recipes out there for homemade

herbal mouth washes that use various essential oils.
Rebecca