"Stará se o něho Žofie."

[Pollyhs]

Could I also say Zofie se o nej stara

[endless_sleeper]

You can. The meaning of the sentence is changed though. Generally speaking, put the most emphasized thing at the end.

'Žofie se o něj STARÁ.' (as opposed to doing something else)

'Stará se o něj ŽOFIE.' (as opposed to someone else)

[Pollyhs]

And why can't we always start with the proper nouns?