it depends if you want to emphasize the thing that you weren't told. It's not at all unnatural to have that in there, although you are right that, depending on the context, it might be superfluous. However, especially since the 'das' comes first here, that implies an emphasis on the thing, so I would argue that including 'that' in the English translation is a stronger one.
You haven't included your suggested translation, so taking what you say literally and replacing "told" with "said" in the above translation, you cannot say in English "They would have said me that". However you can say "They would have said that to me" and that is an acceptable translation of this sentence.
In this case there is a direct object, "that". There is only a "me" in between. As i can see from this article
you use "tell" when you have a receiver of what you want to say.
What are you trying to convey by posting these sentences? The word order in German is different than the one in English. So if you really want to learn German you should not try to translate word by word, but get a feeling for the rules. And here the rule is that infinitives and participles go to the very end of a sentence.