ArgumentCountError: Too few arguments to function Drupal\hal\Normalizer\ContentEntityNormalizer::__construct(), 3 passed and exactly 5 expected
#0 in the stack trace contains Drupal\hal\LinkManager\LinkManager. That was ultimately the clue that the missing services were in our custom rest module. Whereas three services in our custom module was okay in Drupal 8. In Drupal 9, all five need to be included.
So yes, upgrading a Drupal 8 site to Drupal 9 works as advertised. It is, of course, still a lot of work. :-)