How to create a pdf file with embedded links to other documents in pdf format?

You can embed hyperlinks with Adobe InDesign. See https://helpx.adobe.com/indesign/using/hyperlinks.html
You could host linked files on a web server. That makes especially sense if you create multiple PDFs for download. If you e.g. deliver documents on an USB flash drive you could also link to local files.
It's possible to add hyperlinks in Adobe Acrobat, too. I think that is more limiting.

 

Most job applications from that I know are sent by email. Making linked PDFs available for download via http should make sense for this.
If someone is handing out a job application, that's still going to be printed on paper in most cases.

But why don't you include all pages in one PDF without linking? If you scan and edit all documents properly you can make a good quality grayscale 10 page PDF that has about 1MB. A hyperlink needs to be clicked, for external links usually a message will pop up, asking if you trust the link... Would you trust a link someone unknown sends to you? Maybe linking is not the best strategy for common job applications. Sure, there might be exceptions. Internal document linking to mentioned topics/qualifications could make more sense and no security warning will pop up either.

 

Do they understand that linking requires a web server? Sometimes people ask for things without understanding what's required.

If they did fully understand what's required, they'd either tell you what addresses to use, or refer you to a webmaster or web producer who can tell you what those addresses should be. You can't just make up addresses and hope they'll work.