In this sense (and context) "what" and "that" aren´t usually interchangeable.
Of course you can use both "What a shame!" or "what a pity!", but "that´s a shame." or "that´s a pity." aren´t so strong an statement.
"Oh, that´s a shame" would convey a feeling of outrage close to "what a shame!", anyway it could be a just a way of expressing sarcastic sympathy for somebody's misfortune when said in a very nonchalant tone. Indeed, the tone is what, somehow, will stablish if they can interchangeable or not.