I figured it out.Not sure how this happened, but somehow the Renderer (in Project Settings > General > Video Rendering and Playback) was set to Mercury Playback Engine Software Only. I changed it back to CUDA and all is good
Premiere's export may be hitting some limit with the other settings you chose. Can you use FFMPEG (or a program like Lossless Cut https://github.com/mifi/lossless-cut) to simply add the caption track vs re-rendering? No quality loss this way too.