Ok - I've been trying a few things. Ive got my Edge, 595 and Android Phone paired together and working as expected. No problem.
Well - not much - I'll post some pics first though.
The screens that you posted came up on my 595 without too much issue.
This one is what I got when I selected Home Screen -> Apps -> Phone

- 595 Phone - 09.png (29.28 KiB) Viewed 12550 times
But it will only get to this page if the phone is connected AND the headset is connected.
======================================
This is the screen that I get if you select from the Map View page -> 3-bar menu -> phone . But it slides back out of view after about 10 seconds.

- 595 Phone - PopUp.png (48.16 KiB) Viewed 12550 times
======================================
This is the screen that I get for an incoming call - when the map screen is shown on the 595.

- 595 Phone - 14.png (48.15 KiB) Viewed 12550 times
This side screen only shows up if the map is displayed - otherwise a message pops up in a big white box.
======================================
Once everything is paired and working, it automatically reconnects. Very reliably. But it takes about 30 seconds to a minute for the phone and the haeadset to pair and for the Zumo to realise that everything is as it should be.
Unfortunately , the Zumo battery doesn't tend to last that long before it starts shutting things down - so it is prudent to have the Zumo 595 plugged into a charging socekt while you are testing it out.
======================================
To get all of that working then the 595 has to be first paired with the Headset. (It doesn't have to be done first, but it makes sense so that you can test that sound is being played from the Zumo. You cannot test anything on the phone until you have the sound set up.
I set my Zumo to be the second phone on the Edge. This is so that if I want to use the App to manage the Edge form my phone , I can connect that as the first connection and not accidentally over-ride my phones connection to the Zumo.
======================================
Pairing the Caro Edge to the Zumo on the second channel.
1. Turn on Cardo - 5 second press the left button.
2. Turn on Zumo. Tap the BT icon or select Settings -> BT
3. If you already have a pairing to the Edge but sound isn't comeing through , then clicke ont he Edge device on the Zumo and select Unpair.
4. On the Edge, press the bottom button for 5 sceconds (3 beeps / Phone pairing)
5. Tap the bottom button twice, roll the wheel forward. (2nd phone pairing)
6. On the Zumo tap Search for Devices, and when the screen changes and the Edge device is shown, select it. (2nd Phone Connected)
----
7. Check that sound is coming from the Zumo to the headset. Play music - or From the main screen -> Volume -> Spanner -> Button Sounds (tick)
Every time you tap on a button ont he screen, you should hear a click.
======================================
Now to pair the phone.
1. If the phone and the Zumo already know about each other, but the phone is not connected, then you have to delete the pairing from the Zumo and you also have to delete the Zumo from the phone. Unpair them at both ends.
2. Get the phone ready to start to search for new devices.
3. Start the Zumo searching for new devices. Settings -> Bluetooth -> Search for Devices.
4. They should find each other. When Pairing my ipad, the Zumo displays a number that I have to type in on the phone. The android just asks to confirm that the numbers match
If they do not find each other you are going to have to do the Bluetooth Rain Dance - which basically means disconenct everything else that the phone may be connecting to or hunting for. Restart both machines from cold. My phone would not connect to the Garmin. I ended up deleting my other garmins, and my cheap BT headset and a couple of other devices that I regularly connect to at home - and then rebooted both machines. Complete power off. That worked perfectly. The two devices found each other straight away.
This is the minimimum that you want to see on the Zumo 595's Bluetooth Screen.

- 595 Phone - 06.png (24.17 KiB) Viewed 12550 times
Phone should have the phone icon. The notifications and Smartphone Link icon do not matter at this stage. If you have the Smartphone Link App loaded onto your phone - this provides traffic and weather information amongst other things - then you may get everything lit up - as shown below.

- 595 Phone - 07.png (23.88 KiB) Viewed 12550 times
If the phone is properly connected, then you will be able to see this set of icons from Main Screen -> Apps -> Phone
- which I often use to make sure that the Zumo is actually talking to the phone and has received that information.

- 595 Phone - 10.png (26.3 KiB) Viewed 12550 times
Voice dial seems to activate voice instructions to the phone - rather than just the dialling mechanism - so "Hey Google" might well work. I haven't played with this - and it will probably be different from the Apple, which I cannot check.
For the Android, the "Smartphone Services" entry in the Bluetooth list offers no options. But with an iphone connected it opens up a set of options which you can select - indicating which notifications (email, messages, Facebook, etc) you wish to have the Zumo display on the screen. For the Android, these have to be selected in the Smartphone Link App itself. Whch isn't nearly as convenient.