coming from a caged bird perspective, i prefer natural branches because always perching on the same surface day after day can cause sores on their feet. that being said, chickens tend to spend most of their day on the ground, not on a perch, so they don't tend to develop sores as easily as a caged bird. whatever you choose for your bird, by varying the size, angle, etc, your birds can choose which is most comfortable to them.
but when choosing natural branches, keep a couple things in mind. choose a wood that is safe for the birds, from healthy trees, that has not been sprayed with pesticide or fertilizers recently.
my personal choices for branches are dogwood, maple, poplar, and most fruit trees. these are all safe woods. granted chickens aren't as likely to try chewing the wood as a caged bird might, but why take the chance? as for size, since chickens aren't 'grippers' like many parrots and finches, i would recommend finding a branch that is at least 1-2x the diameter of the length of the chicken's foot.
and no, i wouldn't paint them.