I guess you do not have the original layout file nor any high cost PDF surgery tools like the already mentioned Pitstop, you have only a CMYK color PDF - the same as the linked version. If you have a 1000 page book or there are also other colors than white, grey and black, this receipe is probably useless.
You can place your PDF to an Indesign document which has a white background rectangle in every page(=not an empty page) and on the top there's the wanted color rectangle with blending mode Overlay; that's one of the transparency effects. It colorizes all grey, but leaves black and white. To make the colorization happen in Indesign the transparency flattening color space should be changed RGB. Use high resolution flattening option. Do not expect an exact color with misused color modes, you must adjust it for right final result.
An example of the result:

You must layer the colored shape page by page. A script writing guru might find how to program it. I skip it. The white background can be on a master page. The colored rectangle maybe could be placed on top for ex. by placing a full length document which has nothing, but the colored rectangle on every page, got from a master page (not tried).
Use Adobe PDF printer to get the transparency flattened as wanted. Exporting as interactive PDF (=RGB, for screen only) from Indesign left for me an unflattened PDF where the edges (=anti-aliasing zones) of all black shapes were also colorized in PDF viewer. It fortunately was possible to be fixed by flattening the transparency in Acrobat Pro.
My harms can be caused by using legacy versions of Adobe stuff. Modern Indesign can have things differently.
If you cannot use Indesign + Acrobat Pro the case becomes much trickier, but not impossible. Many programs can open PDFs for edits, but to avoid font pirating lawsuits the fonts of the texts are either substituted or outlined (=changed to same looking curves). The job was possible at least in Serif Affinity Publisher.
Drawing programs can be used, too but they allow to load only one page at a time, which is tiresome.
Simply recoloring the grey shapes in a drawing program or Affinity Publisher is complex because there are tricky multilevel groupings. It causes you cannot select shapes by color. You can select items one by one, but that's what you wanted to avoid.