@Sam100: Head into Settings > Apps > 3 dots (top right) > Show System Apps > Bluetooth Share / Bluetooth Test > Storage > Clear cache / data. Please can you also try restarting the phone in Safe Mode via the steps below and attempting the connection again. If you're able to proceed without issue then please restart the S8 and delete any recently installed third party apps.
Turn the device off > Press and hold the Power key > Release the Power key when the S8 logo appears > Press and hold the Volume Down key immediately after releasing the Power key > Continue to hold the Volume Down button until the device finishes booting.
If the problem persists then run the hardware test: Samsung Members app > Diagnostics > Test Hardware > Run through the Bluetooth test. If you get any errors or 'fail' messages then you may wish to visit a Samsung Support Centre to arrange an inspection. To find your nearest one please check the following link, select 'Mobile Device' and enter your post code.
http://www.samsung.com/uk/support/servicelocation/