How do you change class in the game? I've completed the four shrines but no sign of anything related to the class change.

To change your class you can either -

1. Go to the desert town and make a deal with the demon.

2. Collect the four treasures, kill the demon in the desert, and then go to the far north town which is empty and make a pact with the angel.