Ik ben zelf niet in die regio geweest (we hebben ons uiteindelijke beperkt tot Kuching en omgeving, in Sarawak), maar heb destijds redelijk wat research gedaan. Wat ik een keer tegen kwam in een reisverslag was dat mensen een auto gehuurd hadden en vanaf Kota Kinabalu naar het noorden gereden waren. Daar zijn een aantal leuke stranden, dorpen en jungle. Wat ik ook zag en me aantrekkelijk leek was om met de auto richting Mt Kinabalu te rijden. Je hoeft niet per sé de hike naar de top te maken, het gebied rondom de top is ook al prachtig en je kunt daar ook wat wandelen (zonder met een guide naar de top te gaan). Er zijn daar goede wegen, dorpjes en guesthouses. Je zit dan wat meer rondom de voet van de berg.
Ik zou als ik jullie was dus gewoon een mini-roadtripje doen van een paar dagen en dan een dagje strand en een dagje bergen meepakken, en lekker rijden

De wegen die ik in Sarawak overal zag waren overigens heel prima qua conditie.
Overigens hebben wij Mulu NP ook vanwege budgettaire overwegingen geskipt. Vanuit Kuching moesten we dan twee vluchten boeken om bij het park aan te komen, wat een behoorlijk prijzige aangelegenheid was, om dan vervolgens een guided-tour met overnachtingen te boeken, ook duur en dan moesten we weer terugvliegen naar Singapore of mainland-Maleisie. Ik vond dat allemaal nét wat te gortig worden. Daarom zijn we in Sarawak gebleven waar we, naast Kuching, Bako NP bezochten (echt fantastisch!!) en een paar dagen verbleven zijn in een homestay bij locals in de jungle.
Veel plezier op Borneo!