You softproof with the perceptual intent selected and edit the colors to look the way you want. It will probably be easiest to apply the edits to one image and then copy those changes to all of the other images as a general approach.

Another option is to turn on the out of gamut warnings and edit the images so that nothing is out of gamut... then relative/perceptual intent will make no difference.

Then export those images as sRGB jpegs for the purpose of being printed by that shop (maybe rename them to make that apparent).

1. yes
2. no

Edit to answer added questions:

3. Relative intent only takes out of gamut colors and changes them to the nearest in gamut color. Whereas perceptual intent changes the color to the nearest in gamut color and adjusts the other colors so they have the same relative difference. If you picture a histogram with out of gamut colors outside the ends, relative will just pull them into the very ends of the histogram leaving all of the other colors alone. Perceptual will pull them in by shifting the whole histogram. That's why relative seems darker... it's packing up the end (certain colors).

4. You cannot encode relative or perceptual, it really has nothing to do with the color profile. It is not an edit and it doesn't change the file/data in any way. It is a simulation of how the end device will handle colors that it cannot otherwise use/reproduce. The point of softproofing is so that you change the colors so that you get back something closer to what you want/expect. Your choice during softproofing does not change the fact that the end device is going to use perceptual intent (in this instance).

Normally you do not know how the end device will handle out of gamut colors; the choice of relative vs perceptual during softproofing is a personal choice in how you change the colors so that they are all in gamut... then the end device won't need to use either method and it won't matter; the end result will be as expected (hopefully). Printers typically use perceptual because relative is more prone to blocking/banding.

Generally, if there is very little out of gamut the relative intent is better, because it leaves all of the in-gamut colors alone. But if there is a whole lot out of gamut the perceptual intent is usually better because it tries to maintain the relationships between the colors. Note that changing between relative/perceptual during softproofing does not move all out of gamut colors w/in gamut; that is still your job. The image display and histogram is only simulating what the result will be if you don't. And it is only a simulation... an RGB projected display (monitor) cannot exactly duplicate a CMY reflective display (print).