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.