We got some messages like:
GitHub API Usage: Current quota has 3900 remaining (78 over budget). Next quota of 5000 in 59 min. Sleeping for 1 min 39 sec
After investigation we found, that GitHub rate limit remaining and resetDate sometimes increase (out log part: https://gist.github.com/bozaro/1b64f3eb617af97b5f4c822cac870212).

I could not figure out how to implement the correct throttling.

We disable trottling (https://github.com/jenkinsci/github-branch-source-plugin/pull/237) and minimal remaining value for 14 days is 2986). So without throttling we never exceeds rate limit.