Cross dissolve introduces blocky artifacts
As this answer alludes to, it's probably an issue with the target bitrate:


  800kbps is very low for 1080p. It probably works for lecture notes
  because there isn't much change from frame to frame, but blocking
  occurs during the transition because there isn't enough bandwidth to
  handle all the changes. Here are a few alternatives:
  
  
  Keep average bitrate low but increase the maximum bitrate; this will potentially provide headroom for the transitions
  Use a wipe or slide transition instead of fade so that only part of the image changes at a given time
  Do not use a transition; just cut to black (or white, or a new title); this alternative will likely produce the best results
  
  
  A few notes about your other settings:
  
  
  Render at Maximum Bit Depth matters if processing and exporting at 10+ bits per channel; you can leave it unchecked for H.264
  Maximum Render Quality is intended for use when exporting at smaller dimensions than the sequence
  Changing Stream Compatibility to Standard and Profile to Main or High will provide better compression via CABAC encoding; however, the
  compressed file might not play on some devices (Main Profile will be
  more compatible than High)
  Consider publishing low-bitrate versions at lower resolution (1280x720 or even 854x480) and encode 1080p at higher bitrate;
  similarly, retangular pixels (1440x1080) can help, but the video won't
  play correctly in many media players
  


Turns out when I chose H.264 as the format and Match Source - High Bitrate as the preset, the default target bitrate was very low (10 Mbps). For a 4K video, you probably want to use VBR, 2 pass with Target Bitrate set to 44 Mbps, and Maximum Bitrate set to 56 Mbps.

This also explains why my resulting videos in Premiere were originally much smaller than similar ones created in Final Cut Pro.

If you're uploading to YouTube, you can use the YouTube 2160p 4K Ultra HD present, which will choose a respectable 40 Mbps. The one caveat is that there are two versions of "4K" and there's a possibility that your source clips will get cropped with these export settings. To verify, you should temporarily "match source" on the width/height of the video, and verify that those are the same as the YouTube preset you chose.

Although even with this preset, you may want to follow some of the suggestions in this article and tweak it to use VBR, 2 pass. Although the low bitrate mentioned in the article should probably be avoided.