Place it into Adobe Photoshop. If you cant afford it, torrent it off Pirate Bay or something, I don't care. Its expensive.

There is absolutely no reason to pirate or buy Photoshop for this - GIMP does the job just fine. Here's how to do it on GIMP, based on OP's tutorial.

1. Press F10, save map, open it on GIMP. It'll open as a single layer; I'll call it the original layer.
2. Click on "Crop Tool" (or press Shift+C), select the area you want, press Enter.
3. Check the layers list. Right-click on the single layer there, click "Add Alpha Channel".
4. Click on "Select by Color Tool" (or press Shift+O), click on the colour you want to select. If you want to select more than one, just press Shift while clicking on the other colours.
5. Click on "Edit" > "Cut" (or press Ctrl+X), click on "Edit" > "Paste" (or press Ctrl+V).
6. Check the layers list, probably at your right. Rename that "Floating Selection" to anything you want, so it becomes a separated layer.
7. If you want to cut more countries like that, click on the original layer and redo the steps 4 to 6. Odds are you won't need though.
8. Click on File > Open as Layers (or press Ctrl+Alt+O), select a texture you want. Move it to the bottom layer (drag and drop or click on the down arrow near the layers list). Let's call it background layer.
9. Adjust the opacity of the layers the way you want with that slider above the layers. Don't do it for the background layer (keep it at 100).
10. For labels: Click on the Text Tool (or press T). Configure the font, size, colour, this kind of stuff. Click anywhere on the map and write it.
11. If you want to rotate the text, there's a bunch of tools for that on the left side. If you want to distort the text, right-click its layer, click on "Layer to Image Size" and use the Cage Transform tool.
12. To add a crest or something like this: import the picture you want to use as crest, just like we did on step 6, but do not move it to the bottom layer.
13. When done, click on File > Export As... (or press Ctrl+Shift+E). Select a name and a type (if you don't know the type you want to save it as, select PNG Image (*.png). Congrats, you have your map :)