agar-agar is sometimes called japanese or vegetarian gelatin and is made out
of seaweed.

arowroot starch, or powder, is from the arrowroot plant which is a tropical
perennial herb whose food value lies in its starchy roots.

so both of these should be considered paleo.

JoAnn.