As far as HOW Ulim got to Roshar, I had a theory about Gavilar using rudimentary rockets to travel between the planets.
If you remember in the ROW prologue, when Navani eavesdrops on Gavilar and the two Heralds (Nale and Kelek), she hears one of the Heralds say, "...Being able to bring them back and forth from Braize doesn't mean anything. It's too close to be a relevant distance." She then hears her husband say, "It was impossible a few short years ago. This is proof. The Connection is not severed, and the box allows for travel. Not yet as far as you'd like, but we must start the journey somewhere."
My theory is that Gavilar has used his various connections to worldhoppers to either use, or build a basic rocket ship, probably unmanned, to ferry voidspren back and forth from Braize. This would fit with the idea that it's incredibly expensive/difficult to get voidspren in large numbers, like Axindweth and Venli both mention later.
As far as the Heralds are concerned, Kelek wants out of the Roshar system BAD. He's desperate, but his Connection to the Oathpact and his incredible amounts of investiture make worldhopping by way of Shadesmar impossible. So maybe his next best bet would be physically flying to another system? "There's more here, Nale! This is important! I want out. This is the only way..." Nale might want out as well, or he may be simply curious. He may also just be spying on the whole project to see when he needs to put a stop to it, as evidenced by his interaction with Venli shortly after the meeting with Gavilar takes place.
Anyway, that's my crackpot theory. Feel free to punch holes in it.
