In my case, the <mat-paginator> element was inside a container that had an *ngIf on it, which did not render until the data loaded asynchronously. This causes this.paginator to be undefined even in ngAfterViewInit. This causes it to silently fail as MatTableDataSource has no problem with you setting paginator to undefined.
The solution was to move the <mat-paginator> outside of the *ngIf‘d container
Hopefully, this helps someone who is in the same situation as me.