As an old fashioned UK English speaker, I would have used the 'that' in that sentence. Without the 'that' it would sound like (not necessarily read like) two sentences: a sarcastic "What a pity." and a statement implying that I am telling you not to come. Any possible ambiguity is removed by using a word for word translation and, to my ears, it just sounds better.
"kia domaĝo" or "kiel domaĝe" -- "kia domaĝe" is not possible (adjectives don't modify adverbs).