I am using paid Google Apps for Work and it should be working with Google Sync. Firstly, I did it like this:
First, in your Google Apps administrator control panel, turn on the
Enable Google Sync setting. (If you don't have administrator
privileges for Google Apps, contact your system administrator.)
In your web browser on your PC, go to Mobile settings for your Google
Apps account, and then enable Google Sync under Service settings.
On your phone, go to Settings Settings icon > Email + accounts > Add
Tap Advanced setup, enter your account email address and password, and
then tap Next.
Tap Exchange ActiveSync.
Enter the rest of the info for your account:
Under Domain, enter the last part of the email address for this
account—for example, if the email address is email@example.com,
enter contoso.com. Under Server, enter m.google.com. Tap Sign in.
from here: Sync Google Email Contacts and Calendars FAQ
I was notified via email for New Device Activation and I enabled the device in Google Apps console . However, the error was still saying 'not synchronized' on Win Phone.
The solution to sync paid Google Apps for Business on Windows Phone Lumia 535 Windows 8.1 was to set up Google account through "Google" option and not Google Sync account through "Advanced options" like advised from Microsoft (upper link).
When you tap on
Google, web app will come out to give your phone right to access Gmail, contacts and calendar. Log in and accept permissions and that's it. You will have your Google Apps contacts, calendar and mail synchronized.