Without Einstein, I think that the discovery of time dilation would be delayed by only a few years. There were a lot of people working in theoretical physics already back then; someone else would inevitably dig through Lorentz' and Poincaré's papers, connect the dots, and say "waitaminute time might be relative". From that, time dilation is a consequence.

In special I wouldn't doubt that Max Planck would discover it.

I'm saying that because, in both science and engineering, often you see almost concurrent discoveries or developments of the same thing, because the "spirit of a time" makes people look at that aspect of reality or that challenge and work with it. The discovery of helium and the development of aeroplanes are examples of that.