Interesting observations.
The only thing that comes to mind immediately is that there are some verbs that involve creation that might also apply to existing objects:
"I bake a cake"
That could either mean creating a cake by baking, or that you take an existing cake and (for some unusual reason) bake it in the oven. A similar (but semantically exceptional) example would be "make a/the bed".
Note that 'paint a tree' in the sense of making art with a tree in it is also a verb of creation, where the meaning is 'render a tree by painting', so studies about the transitivity of verbs might also be of some relevance to you.
But paint is, as you point out, interesting for having all three of those properties. I'm not sure that all/any of those are particularly special in themselves, but it would be interesting to figure out why and whether there is a more general pattern or just an ambiguity in that particular verb.
Of course some near synonyms do seem to pattern similarly, like "to color" but that's in narrower/more obscure usage in at least one of the senses. Maybe "to design" could work as well.
Anyway, interesting to think about, and I'll keep thinking about it and if I come up with more I'll reply again.
--
Regarding the cases, why specifically do you think one is accusative and the other dative? That may be reasonable under some analysis, but English doesn't really give any distinction (just the 'oblique') morphologically or otherwise in terms of surface syntax. Looking at a cognate language, if there is one with the same ambiguity, could be helpful. Maybe German:
http://dict.leo.org/german-english/malenBut I don't see clear evidence in that (usually very helpful) dictionary for this particular question, so you might need to investigate in more detail.
--
Edit:
Verbs of filling and emptying also display some overlap:
I filled/emptied the water.
I filled/emptied the container.
And maybe operating:
I drove the car/course.
I flew the plane/distance.
Note that the overlap with the
same object is rarer in these cases but technically possible:
I filled the water with dye.
I flew the remote controlled helicopter the [distance of the] plane.
Paint stands out as remarkably versatile, though, and the others don't clearly fulfill all three criteria.
But by the way, I'd say only 'paint [on] the tree' can be used intransitively ('paint'), as in "Did you paint?", because that does not imply the end of the event (telicity) so there would not necessarily be anything (e.g., a painted tree) created, although a physical tree would indeed have become (partially) covered in paint. So "Did you fly?" seems reasonably parallel.