Your best bet would be PVA (Poly vinyl alcohol), which is a water soluble plastic and usually the base of wood glue or water based paper glue.
Dilute it in warm water and soak your paper in it.

Starch is too stiff and crumbly for that use case.

Artist here. Gesso makes flimsy paper more durable, better able to withstand wetness, layering. I've used spray adhesive, various liquid adhesives that can turn paper more stiff, solid, crisp. Maybe try calling an art supplies store, they might have ideas

Do a search online for paper mache. I think that's what you want.

Depends on the project, and the paper... or more exactly, the ink on it.

If the catalogs are printed with water based ink, then you can soak the paper in water and make paper pulp, then mix in whatever hardener you want: corn starch, white glue, any wood glue, or even epoxy (but mind the toxicity and curing times).

If they are printed with toner (basically fused plastic), then you may have a harder time separating the pulp. You can shred the paper and throw it into boiling water, stir well then let it rest to hopefully separate the toner by density, then use as the pulp above.

Or... you can use the plastic to your advantage, by heating it up to fuse one piece of plastic/toner coated paper to another (toner should fully melt at around 130C), with a clothes iron, hair iron (set to 130-150C, and through a sheet of non-toner paper or some kapton tape so you don't fill them with toner), or carefully with a heat gun (better if it has temperature control, 150-200C should be a safe range). Or... use glues, but plastic ones this time, like lacquer, super glue... and I guess epoxy should work in either case.

Depending on the project, you might even encase it fully in epoxy, either a two part or a UV reactive one (but probably avoid 3D printer resin, it's formulated to only react in a thin layer at a time).

PS: from the numbers alone, it should be possible to melt the toner away from the paper in a 120C liquid, but you may have a problem doing that with water (a high pressure cooker comes to mind, which would get ruined afterwards; salt might help, but not sure how would that impact the pulp; maybe high temperature steam in a microwave could work, but that gets dangerous pretty fast). Oil would be an obvious choice, but it would coat the pulp, then you'd have to use a detergent... quite a mess.

Depending on your use case, if you want something stiffer you could brush each sheet with slow curing epoxy resin, then layer and press it to create some DIY micarta (yes, micarta technically uses phenolic resin, but epoxy should work fine for most uses).

Often don't need corn starch, but depends on makeup of the paper & what you want for the end use, leave to dry. Can add glues for other effects.

Tear up pieces, soak in water, squeeze out excess water, shape as needed. Adjust size of torn pieces for different structural effects, from slurry you can pipe for definition & brittle strength or compression through to large overlaid sheets for sheering strength & flexibility)