Although I have never been to the other destinations, I do know Buzios, Rio, and Paraty quite well. I suggest going to Sao Paulo first and then catching a bus to Paraty. It's a great town with lots to see and do. You can do nature and agriculture tours, boating tours, or just head to the many private and quaint beaches. At night, the food in town is wonderful. Having car can help speed things up.