Ok the less technical answer is as follow:
Your sample has a lat/lon grid which I am almost certain will be WGS84, grab 4 corners that have clearly lat/lon labelled and georeference considering those points and WGS84 data, you could add a few more points since its a grid to minimize distortions
By the way you should just download QGIS from www.qgis.org its open source and has georeference capabilities, Avenza PDF maps accepts geotiff also that you can upload to the store for approval (if you intend to sell/provide) or you can read directly from your device
P.S. you will need to convert from PDF to JPG probably
Regarding the original posted question - I don't think this is possible without somehow rasterizing the original PDF. In regards to the bounty, I am posting the following as an answer.
Go to http://www.frontenacmaps.ca/Html5Viewer/index.html?viewer=Public, zoom to your area of interest, add bike trails/roads etc., click on the wrenches icon in the upper-right corner of the map, on the 'Printing and Exporting tab, export the map as a GeoTIFF (GeoTIFF has location information stored in the file).
Open the exported geotiff file in QGIS 3.2 and warp/reproject it to WGS84 coordinates.
Remove the original Export.tif file. Right-click in Layers menu -> Remove Layer.
Make sure the Coordinate System is set to WGS84. Click on the coordinate system icon in the lower-right corner of QGIS, set it to WGS84.
Add a new Layout.
Set the page size.
Add a new map canvas, size it to the page, double-check coordinate system is correct, print it as a Geospatial PDF.
ADJUSTING MAP CONTENTS NOTE: Pan and zoom around in the map window with the tool pictured below. Activate tool, click in map canvas, wheel-mouse to zoom in/out, press/hold mouse button and drag mouse to pan etc. Print to PDF.
Open in Acrobat. Look for the 'Measure' Tools. Click on 'Geospatial Location Tool' -> click in the map -> you should see values in the coordinate display and be able to take distance measurements etc.
Best Answer
ArcGIS Pro 2.4 (released a few weeks ago) quantizes complex vector geometry based on your chosen DPI, thereby potentially drastically reducing file size of your exported PDFs. If you've not yet updated, it might be worth a try to see if this helps with your processing problem.