In Bacalar, the ADO bus stop is just right next to a gas station.
In the shop next to it they accept items of luggage for a small fee each.
The only catch is that you need to get them before 22h. I needed them around 00h15m. A bit before the bus I had to get.
The pickup hour is probably negotiable. When I asked, the person immediately said he would be available. I didn't really feel comfortable with this solution as if the person forgot about me I would lose either my bus or my luggage.
In the end, I took a different road. I looked up the cheapest possible place to spend the night in Bacalar, went there and just left the luggage. I ended up paying the same as if I left it in the gas station shop, next to ADO. This solution, however, might not work always, if the cheap places are all booked. Even if full, you can always try to go to one of them and negotiate a price to leave the luggage. Bacalar is rather small and has enough offer to make this feasible.
Most ADO Bus stops have places to leave luggage. Only small ones don't. I believe this might be a good strategy for other small places.