I'm trying to solve this question.
Following the hint, the Fourier inversion formula gives me : $$ \big| f(x+h) - f(x)\big| = \left| \frac{1}{2\pi} \int_{-\infty}^\infty \widehat{f}(\xi) e^{i(x+h)\xi}\; d\xi ~-~ \frac{1}{2\pi} \int_{-\infty}^\infty \widehat{f}(\xi) e^{ix\xi}\; d\xi \right| \\=~\frac{1}{2\pi} \left|\int_{-\infty}^\infty \widehat{f}(\xi) \big(e^{i(x+h)\xi} - e^{ix\xi}\big) \; d\xi \right| \\\leq~ \frac{1}{2\pi} \int_{-\infty}^\infty \big| \widehat{f}(\xi)\big| \cdot \big| e^{i(x+h)\xi} - e^{ix\xi}\big| \; d\xi \\= \frac{1}{2\pi} \int_{|\xi| \leq \frac{1}{|h|}} \big| \widehat{f}(\xi)\big| \cdot \big| e^{i(x+h)\xi} - e^{ix\xi}\big| \; d\xi ~+~ \frac{1}{2\pi} \int_{|\xi| > \frac{1}{|h|}} \big| \widehat{f}(\xi)\big| \cdot \big| e^{i(x+h)\xi} - e^{ix\xi}\big|\; d\xi$$
I used this estimate for $|\xi|> \frac{1}{|h|}$ : $$|e^{i(x+h)\xi }-e^{ix\xi}|\leq 2.$$ This gives me $$\frac{1}{2\pi} \int_{|\xi| > \frac{1}{|h|}} \big| \widehat{f}(\xi)\big| \cdot \big| e^{i(x+h)\xi} - e^{ix\xi}\big|\; d\xi \leq \frac{1}{2\pi} \int_{|\xi| > \frac{1}{|h|}} \frac{M}{|\xi|^{\alpha+1}} \cdot 2\; d\xi \\= \frac{M}{\pi} \int_{|\xi| > \frac{1}{|h|}} \frac{1}{|\xi|^{\alpha+1}} \; d\xi \\=~ \frac{2M}{\pi} \bigg[\frac{1}{-\alpha|\xi|^{\alpha}}\bigg]_{\frac{1}{|h|}}^{\infty} \\\leq \frac{2M}{\alpha\pi}|h|^\alpha$$ I'm not sure if I used the Big O condition correctly though.
Moreover I cannot find a suitable estimate for $|\xi|\leq\frac{1}{|h|}$.
My starting point is, of course, your work.
$$ \big| f(x+h) - f(x)\big| ~=~ \left| \frac{1}{2\pi} \int_{-\infty}^\infty \widehat{f}(\xi) e^{i(x+h)\xi}\; d\xi ~-~ \frac{1}{2\pi} \int_{-\infty}^\infty \widehat{f}(\xi) e^{ix\xi}\; d\xi \right| \\=~\frac{1}{2\pi} \left|\int_{-\infty}^\infty \widehat{f}(\xi) \big(e^{i(x+h)\xi} - e^{ix\xi}\big) \; d\xi \right| \\\leq~ \frac{1}{2\pi} \int_{-\infty}^\infty \big| \widehat{f}(\xi)\big| \cdot \big| e^{i(x+h)\xi} - e^{ix\xi}\big| \; d\xi \\\leq~ \frac{1}{2\pi} \int_{-\infty}^\infty \big| \widehat{f}(\xi)\big| \cdot \big| e^{i(x+h)\xi} - e^{ix\xi}\big| \; d\xi \\=~ \frac{1}{2\pi} \int_{|\xi| \leq \frac{1}{|h|}} \big| \widehat{f}(\xi)\big| \cdot \big| e^{i(x+h)\xi} - e^{ix\xi}\big| \; d\xi ~+~ \frac{1}{2\pi} \int_{|\xi| > \frac{1}{|h|}} \big| \widehat{f}(\xi)\big| \cdot \big| e^{i(x+h)\xi} - e^{ix\xi}\big|\; d\xi \\\leq~ \frac{1}{2\pi} \int_{|\xi| \leq \frac{1}{|h|}}\frac{M}{|\xi|^{\alpha+1}} \cdot \left| 2i e^{i\left(\frac{\xi ((x+h)+x)}{2}\right)}\sin\left(\frac{\xi(x+h-x)}{2} \right)\right| \; d\xi ~+~ \frac{1}{2\pi} \int_{|\xi| > \frac{1}{|h|}} \frac{M}{|\xi|^{\alpha+1}} \cdot 2\; d\xi \\\leq~ \frac{M}{2\pi} \int_{|\xi| \leq \frac{1}{|h|}} \frac{1}{|\xi|^{\alpha+1}} \big| \xi h\big| \; d\xi ~+~ \frac{M}{\pi} \int_{|\xi| > \frac{1}{|h|}} \frac{1}{|\xi|^{\alpha+1}} \; d\xi \\\leq~ \frac{|h|\cdot M}{2\pi} \int_{|\xi| \leq \frac{1}{|h|}} \frac{1}{|\xi|^{\alpha+1}} |\xi| \; d\xi ~+~ \frac{2M}{\pi} \bigg[\frac{1}{-\alpha|\xi|^{\alpha}}\bigg]_{\frac{1}{|h|}}^{\infty} \\\leq~ \frac{|h| \cdot M}{2\pi} \int_{|\xi| \leq \frac{1}{|h|}}\frac{1}{|\xi|^{\alpha}} \; d\xi ~+~ \frac{2M}{\alpha\pi}|h|^\alpha \\=~ \frac{|h| \cdot M }{\pi} \bigg[ \frac{|\xi|^{1-\alpha}}{1-\alpha} \bigg]_{0}^{\frac{1}{|h|}} ~+~ \frac{2M}{\alpha\pi}|h|^\alpha \\=~ \frac{|h| \cdot M}{(1-\alpha)\pi} \frac{1}{|h|^{1-\alpha}} ~+~ \frac{2M}{\alpha\pi}|h|^\alpha \\=~ \frac{|h|^\alpha \cdot M}{(1-\alpha)\pi} ~+~ \frac{2M}{\alpha\pi}|h|^\alpha \\=~ \left(\frac{M}{(1-\alpha) \pi} + \frac{2M}{\alpha \pi}\right) \cdot |h|^\alpha.$$
I copy-pasted some of your lines. I hope there's not misprints.