Is it possible to pair wheel sensors with an Android phone GPS?
The wheel sensor add on will do quite a bit to improve the accuracy of the GPS based current speed. The distance will generally be accurate, to within error values of 50 meters, or so depending on hardware. Most phones, especially with android, are on the lower spec of GPS design, using wifi databases and cellular triangulation to augment the GPS positioning sensor.

They generally use open source maps, like Google Maps, which often change, and are less than consistent about coverage. I would recommend using an ANT+ add on, if you are concerned about exact speed and distance.

Wahoo makes decent ANT+ sensors for the iPhone, but I'm not aware of a quality set up for android. There are too many devices, so it would be difficult to create a single device guaranteed to work across the board on android, even with the same OS version. I assume this is why they haven't made an Android version yet.

Hope that helps.