>I find it hard to find "palecarbs"  -  any suggestions ?

Sweetpotatoes.
Yams.
More tubers (turnips carrots)
Fruit.
Chestnuts.

>Are potatoes considered paleo ?  - (I could eat the peel ;-)

Not by Ray.
They are complete good carbs with vitamins.

But are rather quick insulin elevating.
Not for insulin resistance.

They have a mild (in amounts < 2 lbs) toxin (solanin) as well.
And a potent lectin.

Amadeus