There are many types and variations of Paella depending on the type (senyoret for example has seafood) and the location where you order it. In the capital, Paella Valenciana has Garrofon, Baxoqueta, rabbit, snails and more. If you go to the south (meaning Alicante, not Andalusia), you can see it made with red Pepper which would be a crime in Valencia. However, it's never made with sausage.

That said, you enjoy your rice however you want. Spain loves it's food and we just love discussing it