B767-300 Captain was informed by gate agent that aircraft cleaners deployed escape slide. Maintenance was called; flight was cancelled after determining there was significant damage to multiple sections of the aircraft.

Narrative

After a three day layover in ZZZZ; my clock had reset to local time. The crew arrived at the airport at our scheduled arrival time was advised the airplane would be arriving late from a reposition at a hard stand. Very little was available but we were told it would be a while. Eventually one of the gate agents informed us that the cleaners had blown the 1R door slide (767-300). I spoke with Maintenance Control during several calls and very little information was available. On about my third call I was advised they believed they could remove the slide and empty most of first class and operate under and MEL which would allow us to operate legally back to ZZZ. After a lengthy process of re-accommodating passengers on the next day's flights and reseating passengers; it was discovered that there was significant additional damage to the forward galley; the door; door jam; flight attendant jumpsuit and emergency equipment storage areas in the galley. The flight was cancelled.We were later advised that the flight may reposition to ZZZ via a ferry. The flight crew would have to exit the boarding area to go to operations in another building. There we could receive the new flight plan and brief again. We did that. Upon arrival at operations; our crew was informed that there was significant damage which was not known of in the terminal and a flight release would not like be ready until the damages were repaired and a ferry release document could be made available. After several more hours a release was available but it was made clear that the new release time would not be available for quite some time. I spoke with Maintenance Control and they were still working with local maintenance to survey the damage. They could not commit to a time for repairs or a ferry.I had just transitioned onto the 767 from the 737. I had been experiencing difficulties sleeping during my rest breaks on board all month while on Operational Evaluation (OE). The quantity of information required to be covered during OE is significant. We covered it effectively. However; when it was ever time to go on break; my gears were turning from the notes I had taken and the instruction given by my Line Check Pilots (LCPs). I am certain I'll acclimate to the differences of the new schedule; but it had not happened yet. The ZZZZ trip after OE was the first time I could relax on a trip and with such a long layover I naturally acclimated to the time despite efforts to accommodate later sleep.While waiting for a ride to the airplane and awaiting the ferry release document both my First Officer and Relief Pilot expressed concerns over the lengthy delay having also been up early. I told them I had been up since XA:30 AM. The most recent forecast by operations was for us to depart around XX:00 PM. We had a threat assessment about how long we could wait before safely departing. We elected to wait as long as possible for a new release time. But; one was never produced. I told them I was tired and we discussed break options and the reasonability of how long we could delay. Ultimately; we decided as a crew that it would not be reasonable to operate after such a lengthy delay based upon the time we would have been awake at the new foretasted time of departure. I called the crew planner expressing my concerns and we were placed back on to rest.Upon arrival at operations the following day; we were notified the paper work would have never been ready for the XX:00 PM departure.