If you are thinking only of grammar then this is a very common construction and doesn't need to be avoided. The two "that"s are pronounced slightly differently when speaking. The first one would be with a schwa sound and the second fully pronounced with emphasis.
If it's a stylistic choice then you have some options:
You could contract the "that is" to "that's" to make it sound less clunky. "He mentioned that that's the restaurant..."
You could also so this and drop the first "that". This would make it less formal so more suited to colloquial speech. This is what you've done in the second sentence you tried. "He mentioned that's the restaurant..."
Or you could reorder the sentence to something like "He mentioned that his friend is working at that restaurant". However, this does slightly change the meaning so you would have to decide if it's still appropriate.
Overall, I would say that the sentence is fine as it is. Colloquially I would contract the "that is" to "that's" but that's up to you.
The second sentence you tried is largely the same. The "earlier" doesn't change the "that that" issue so would just depend on if you want to say "earlier" or not.