If you take a look in the-events-calendar/lib/the-events-calendar.class.php in the get_event_link() function you can see how the previous/next event link queries are formed.
You could use this as the foundation of your own query and include a check for the excluded category – or if you prefer to keep some of that logic in PHP form then you could have a loop where each subsequent event before or after the current one is loaded until you find one that isn’t assigned to an excluded category (or until there are no more events left … note this second approach would likely be less efficient than a single query).
I hope that gives you some ideas – it would be great to see what you come up with 🙂