Texture painting seams on joined/loose parts (same UVs, joined mesh)
You have artifacts caused by incorrect topology. Viewed from the side, your topology looks like this:

You have to correct the topology by joining the faces together, so that no face goes through another:

You could do it by first adding loop cuts (CTRL + R), and moving them as close to the extrusion as possible without going underneath it:

Then by aligning all vertices of those loopcuts with the extruding shape by selecting them, pressing G to move and then either X or Y to move along only one axis and on the surface of the shape. If the faces of your shape aren't conveniently horizontal like mine, you can use custom orientation.

Now it's time to align middle vertices of the base with middle vertices of the extrusion: select them one by one, press G twice, and move them along the line.

Next step is to go to Face Selection Mode (press 3), select a few faces and hide them (H). Now Select the faces of the base that you no longer need and press X, then F to remove them. Repeat this for the faces of the extrusion, that you also no longer need. Press ALT + H to unhide the faces.

Now switch to vertex snapping mode:

Go back to vertex selection mode (1), Press Z, then W for wireframe mode, select vertices of the extrusion, that are below the base's top and move them onto newly created vertices:

Press A, to select all vertices, then M, then B to remove doubles. Now your topology should be fixed. Press Z, then S to go back to solid mode.