the paleo objection to coffee is that it comes from beans, none of which are paleo (to the purist) and which are not processable without fire.

Various teas have been used for millenia, soaking leaves is all it takes, although of course boiling water makes tea faster than just letting it soak in the water in the sun.  It's not about caffeine, black tea is just as paleo as green tea.

Black tea, is however to be avoided, as is all dried and fernmented foods if you are treating candida.

That being said, coffee is one of those non paleo foods that do not slow down weight loss in many people.  It does have an  effect on the digestive, or specifically, eliminatory system, creating what appears to be a dependency on it to maintain regular bowel movements.  Constipation is a common side effect of giving up coffee, and explosive diarrhea of common result of reintroducing it after long abstinence.

Kathleen