I think fledarmus was giving the best clue, melting point. All of the compounds should be polar enough to be water soluble. However, everything is relative. What if the homomolecular interactions (crystal) are stronger than heteromolecular ones (water-solute)? Carboxylic acid and amides are well known to hydrogen bond in dimers. If that were true, then we may ask whether the melting points correlate with the solubility (as suggested).
Caffeine, mp 227-228°C
Theophylline, mp 270-274°C
Theobromine, mp 357°C
If we use the melting point as a crude measure of intermolecular forces, then it is strongest for theobromine and weakest for caffeine. You may also find it useful to review the base pairing of DNA and RNA.
The solubility is seemingly not limited by the polarity of the compounds, per se, but rather by the much stronger intermolecular bonds with themselves in their crystalline states. Caffeine, the least able to form hydrogen bonds with itself is now the most soluble in water.