When the sentence reads "The devotees shave their heads before entering the temple," doesn't it gives the picture that each devotee has multiple heads?
"Shave off" is needed when you want to specify the material removed. You shave your whiskers off when you shave your face. You shave off your hair when you shave your head. Many women shave their legs.