I find it works best to leave any fancy textures and whatnot for after the map proper has been finished. I often work in pure black an white until then. You might find this helpful, particularly if you plan to use this map in a novel where you will often be quite limited graphically. When you do add textures, distressing, and whatnot, it's best to be subtle so you don't wash out any important details. You should also try to think about how the "in character" cartographer would have made the map given they probably wouldn't have used Photoshop. Getting rid of the "done on the computer" look is quite tricky.
In a similar vein, you'll need a good idea of the graphical context available to you, and the particular needs of the map. Deciding what gets shown and how is a big part of what makes cartography difficult. A map in a book often won't have room for a lot of detail. You might even have to resort to multiple maps covering different feature sets, or extents in order to convey everything.
Having existing geometry that was drawn without consideration for being on a sphere may hurt your ability to make things work realistically. Particularly if you want to use a graticule, scale, compass rose, or similar indicators of precision. It might be easiest to just abandon any modern ideas of precise scale maps if it fits the setting. (by "campaign" I'm assuming you were playing a high fantasy RPG, probably D&D or a derivative?) Plenty of maps, particularly the few that were actually made in the actual medieval period, were not remotely like modern scale maps. They were more rough diagrams of how things were connected, as far as the people drawing them knew.
Rather than borders you can often get by with just area labels. This is trickier than point labels, but it does look quite nice if you can get the hang of it. Even point labels can be hard to do well though. Labels are one of the things that really make a professional cartographer stand out. It's also one of the things that is really hard to get a computer to do well. The trick with area labels is to try to span the area in a nice smooth curve and to use letter spacing rather than scaling or stretching. You also need to use a proper text along path tool not an envelope deform, otherwise you'll distort the letters which really looks bad. I don't know much about Photoshop, but if you can't do this effectively there, Inkscape is free and is great for labelling maps.