Bother has a couple of meanings, one is "to disturb", and bother with X or bother to X means "to do X given that X is considered a non-required or unimportant task".
"Having painted what he bothered, John began packing his brushes."
This sentence really sounds like you are saying he is painting a person or thing that he disturbed.
You can add the preposition "to" or "with" afterward to clarify this. To is probably the best choice.
"Having painted what he bothered to, John began packing his brushes."
The rules for using perfect or non-perfect tenses in the first phrase are the same as if you were writing a full sentence, the fact that things are a participle phrase (it's not really a clause) doesn't change anything.
Without the had, you are giving the impression John left right after he got bored with painting. With the had, there may have been something happening in between that you talked about earlier or will later talk about.