From what I've learned about amaranth  during my wild edibles research
and study...informal mind you...
Amaranth is good to eat when YOUNG, leaves of older plants are high in
oxalates, which eaten in high quantities is harmful.
The seeds have been gathered and eaten by the local natives of this area
(Arizona) for a long time. I've had some as well, ( not wild gathered,
bought from a non profit called Native Seeds/Search- grow native crops
and try to help native populations get off the American diet which has
increased obesity and diabetes in enormous proportions.)
The stuff I have had was not black...though there were a few specks of
black in there, Can be dry popped, or boiled...
Reminds me a lot of quinoa, if you've ever had that...a similar plant
that grows in the andes, probably eventhe same family now that I think
about it.  iT is a bit gummy and doesn't taste like much...but high in
protein...
As for being paleo...:S tough to say...mostly used by agricultural
native societies...so..probably not...
But better than rice/wheat products probably.

Drcey