These attributes are a bizarre combination of images, some inherited from classical mythology, that don't particularly belong together (though there is a reason behind all of them, and even a smidgen of Scriptural support). Our modern image is a blend between:
- Satyrs, the lust-filled tempters (goat legs, horns, beard)
- Pluto, ruler of the Underworld (pitchfork)
- Fairly generic colour imagery (red and black)
- The mediaeval bestiary (bat wings)
In more detail:
Cloven hooves, horns, tail, shaggy legs and pointed beard - These are the attributes of fauns or satyrs. Compare - though perhaps not if at work, due to goat penis - this image from Wikipedia, a plate from c.520-500 BC. Satyrs are generally associated with lust, barbarity, and bad behaviour, more or less because goats are randy, willful, and eat all your food.. Thomas Boys (1792-1880), writing in Notes and queries, 5 November 1859, suggests the link is with the Hebrew se'irim (hairy wild beasts, probably the object of pagan worship) in Isaiah 13:21, 34:14, etc. In the Septuagint these are daimonia (demons!) and English translations like the KJV often use "satyrs". There may also be some sheep-and-goats connection going on.
Pitchfork - This comes from Pluto/Hades, the Greek god of the underworld. While his usual attribute is a sceptre, indicating his sovereignty, this was sometimes depicted as a bident or two-pronged pitchfork (for reasons that we're not really sure about). His brothers Poseidon and Zeus also used forked weapons - in some sense they mirror one another, as rulers of their respective realms. In the post-classical era, the bident became part of the standard representation. Satan got the same tool because he was put in the same role as Pluto.
For the colour, the devil is not invariably red in mediaeval imagery - in Chaucer, he's green! - and the most common colour is black. Grimm (Deutsche Mythologie) attributes this to the association of the devil with darkness in general, as God is associated with light (most famously in John 1). The night also suggests hiding and secrecy. This has classical precedent - Pluto again - but the notion is pretty generic. Meanwhile, red means blood, violence, and passion. Red-haired people were unfortunately often considered "evil" because of this connection, and Judas was usually shown with red hair. It is also the colour of fire and the New Testament considers hell to be fiery. There's the red dragon in Revelation 12:3 just to cement it further.
Bat wings, at least, are not classical. In the Middle Ages, the devil was depicted with a wide variety of monstrous attributes, indicating that he was unnatural and cursed. Bat wings are one example, and of course bats are pretty inherently spooky, since they are scary-looking creatures of the night. Jeffrey Burton Russell (Lucifer: The Devil in the Middle Ages, Cornell University Press, 1984) says that these wings first appear in the twelfth century, as a corrupted version of (feathered) angel wings.
Russell's general chronology has the 'monstrous' devil image appearing first, thanks to the third-century Desert Fathers. After a fad for 'humanoid' devils (ie, Satan disguising himself as a normal-looking human) from the sixth to eleven centuries, these dominated for the rest of the Middle Ages. They have not wholly disappeared, as a glance at the nearest death metal album cover will confirm, though the wings are the only monstrous feature to be really ubiquitous now.
This particular combination has become more and more "standard". Of course, it is helpful for the viewer to have some standardization, so that we can instantly recognize who in the painting is meant to be Satan. But even this collection of attributes allows for some diversity in interpretation: one can draw a caricatured or cartoon Satan, or an imp, or a Miltonic anti-hero.