Over the years, I've learned to test "what a thing is supposed to do, not how it does it". Usually this would mean to write high level tests or at least to draft up what using the API might end up looking like (be it a REST API or just a library).
This approach comes with the benefit that you can focus on designing a nice to use and modular API without worrying on how to solve it from the start. And it tends to produce designs with less leaky abstractions.
Of course YMMV.