Replacing the passport is the least of it...
I've two visas in my potentially leaked passport (I got the Starwood email). If I'm to replace my passport then I'd also expect the cost - both direct and indirect - of applying for two fresh visas to be covered. Of course Starwood have not provided any way for me to view all the information they regard as having been (potentially) stolen...