Reduce / optimize calling of wp_get_object_terms() when generating permalinks

As you had narrowed it down, since your post permalinks include category WP is trying to figure out how to put them together for every post.

Object Cache

The staple approach would be to optimize efficiency of overall setup, rather than micromanage generations of bits and pieces. If you set up persistent Object Cache for the site, then category information would be transparently cached in memory, rather than retrieved from database every time.

Shortlinks

If that is not an option or you are generating links at a scale that even gives object caching an issue there is a slightly hacky alternative. While you have “pretty” links enabled it doesn’t mean that “not pretty” links stopped working.

You can use wp_get_shortlink() function to generate latter kind of links (/?p=id), which would be much lighter on resources.

They won’t look nice in source, but when visited WP will redirect them to “pretty” versions transparently. Of course excessive redirects aren’t a good thing either, but it’s up to you if the trade-off is meaningful for your circumstances.