From the documentation you linked:
bitly currently institutes per-hour, per-minute,
and per-IP rate limits for each API method
And
High-Volume Shorten Requests
If you need to shorten a large number of URLs at once, we recommend that
you leave ample time to spread these requests out over many hours. Our API
rate limits reset hourly, and rate limited batch requests can be resumed at
the top of the hour.
So it does look like you simply need to slow down your code.