I found in the examples on the material site that the header can be fixed by adding sticky to the matHeaderRowDef:
<tr mat-header-row *matHeaderRowDef="displayedColumns; sticky: true">
For the paginator i added a class to mat-paginator:
<mat-paginator ...
class="mat-paginator-sticky">
with a class based on the answer in the link @frederik provided in the comments
.mat-paginator-sticky {
bottom: 0px;
position: sticky;
z-index: 10;
}