In fact, he never sings the words 'Paint it black'. The message is the same: he wants the door to be black. But the way he wants that effect to be achieved differs. If he says 'I want to paint it black', he is going to do the painting himself. If he says 'I want it painted black', he's going to get someone else to do it.
This is known as the causative (because he is causing someone else to do something). It implies intention and responsibility for the action as if you had done it yourself: if you're accused of murder it's not going to do you any good to say 'I didn't kill him, I had him killed'. (Not all causatives require intention, but with have they do.)
It's a type of passive construction, in the song: the verb is in the passive form and the passive auxiliary be is optionally present, or alternatively have:
I want it (to be) painted black
I had him killed (=he was killed)English doesn't have a regular way of indicating causation. We have this have construction (as in the murder example), or other kinds of passivisation (as in the Stones song), and also the similar make, but we also have causative versions of lexical verbs (so the causative counterpart to eat is feed, where feed means 'cause (someone) to eat'), and some verbs can be causative or not with the same form. Other languages have inflections to indicate causation, or a regular alternation in the verb. Wikipedia tells me that Maori adds the prefix whaka- to make a verb into its causative counterpart, so ako is 'learn' and whakaako is 'teach' (literally 'cause to learn').