For some reason my SP3 is not recognizing my MS Arc mouse surface edition. Changed batteries in the mouse. When I click bluetooth in settings it starts a scan to see whats available but the mouse doesn't show up. This mouse paired and worked fine with my SP2.
Did you press and hold the little button (near the blue light under mouse) for 5-10 seconds to enter paring mode?