Been to Menorca a couple of times, never with a bike but have seen plenty of cyclists out and about. It’s a really lovely island and I don’t think you’d have problems riding anywhere apart from the main east-west road. There were even some dedicated lanes in a few places. From what I recall, most of the roadie action seemed to be around the north of the island and I saw adverts for bike hire and MTB as well so with a bit of internet digging I’m sure something will come up.
There is a path that loops the entire island called the Cami de cavalls which can be walked, biked and horsed AFAIK