In fact it was only one border line to change.
First I changed it in the bastile map, adding a new line some pixels to the right of the old line in pure black and then erazing the old line.
Then I reconstructed the relief-art. In paint.net I added a new layer to the base map pasting the relief art to it. Then I copy-pasted the new border line to the relief art. From the relief art I removed the old border line using the clone-stamp.
Then I ran through the Map Builder tools such as polygon grabber etc. to implement the changes to the relevant txt-files.
Just take a look at the files to see the results.