Every user account has such information as username, email, phone number. I can find these information via AzureAD, MS O365, Exchange Online, MS Teams etc.
Is there any possible way to sync these information with users' contact/phone books on their mobile devices?
So in the result every employee should see all his co-workers in his phonebook.
If users add the organizational mail account (Office 365) on their phone they can simply search for their co-workers. Initial search results will be as found on the phone. After that they will see results from the organizational directory address book.
If you need your users to have the information available as local contacts on their phones, you can instruct your users to follow the guidance at https://support.microsoft.com/en-us/office/outlook-for-ios-and-android-faq-65a01e26-e3c2-4067-bd05-0db6220e5c34 in section "How do I save my Outlook contacts to the default Contacts app on iOS and Android?".