Is the Gibraltar dam feasible?
The Strait of Gibraltar is 14.3km across and up to 900m deep. The highest dam in the world is Jinping-I at 305m. The largest by volume (of the dam itself) is Syncrude Tailings Dam in Canada at 88m high and 18.2km long. For reference Three Gorges is 2.3km long and 181m high, and is the 21st largest dam in the world by volume
The structural problem with the Strait of Gibraltar dam is its height. No other dam in the world is even close. I don't think any armchair material science/math is worth doing to support the science based tag, but I strongly doubt that ANYONE has done a rigorous structural engineering evaluation of a poured concrete structure that could handle this kind of pressure.
Thus the remaining option is simply an earth-filled dam. If we assume, for safety, that we want to make the dam 10km long along the strait (in addition to 15km wide across the strait, and up to 1km tall (to account for the depth). I will assume the depth profile is a simple 'V' (300m depth at the edges, 900m in the middle) with a 600m depth average, then the total volume of fill is 90 cubic km.
90 cubic km of rock weights 240 billion tons, at 2.65 g/m$^3$. Assuming the average rock has to move at least 100km from where it is dug (the Saharan Atlas would be a good source of rock) up to the Strait, that would take 24000 billion km-tons of freight rail, which is more than double the 10000 km-tons of freight rail moved annually, worldwide.
The US produced 2 billion tons of construction aggregate (I couldn't find a world figure) and the world produced 3.2 billion tons of iron ore, so the amount of material that has to be mined is probably an order of magnitude higher than the total annual mining production on the planet.
While I can't say all those numbers mean the dam isn't feasible, I would at least say that creating the dam is a decades long project, considering that the investment in mining equipment and rail transport will probably cost as much as if not more than the actual construction of the dam.
Keep in mind, if you want to actually use the dam for hydro-electric power and not just as a big earthen ocean-stopper, you will need ALOT more concrete. Since total world production of cement is 1.7 cubic km a year, you may have to invest in a lot of concrete production, which in turns means investing a lots of power to drive that very energy intensive process.
Will the Black Sea dam be needed?
The Black sea is good for fishing and helps moderate the local weather. I would not empty if it I didn't have to. If you are already spending trillions/decades on a Gibralter dam, you can probably afford a Bosporus dam as well.
Are any other dams needed to separate the Mediterranean from other oceans?
I don't know if the Suez canal exists in your world, but that would need to be stopped up too.
Are there any other significant challenges that might make it impossible to hold the Mediterranean separate from the world's oceans?
A thought to consider: what would the climate be like in the newly exposed region of the Mediterranean basin? Here are some possibilities. The basin would be in a location with little inflowing moisture. The Sahara desert is to the south, Northern Europe isn't actually that wet and any moisture from there is blocked by mountain systems (Pyrenees, Alps, Dinaric Alps, Balkans, Taurus, etc). It would probably be very dry. It would also probably be very hot since it is so deep below sea level. The Dead Sea is at the same latitude, and is the only comparably deep place on earth. It is not called the Fertile Sea.
The Mediterranean sea is the source of the winter rainfall in North Africa, Italy, the Balkans and Turkey. The massive summer evaporation drives rainfall in the high mountains surrounding the sea, in turn powering the rivers. If you remove the sea, you remove the rain. The whole region turns into one huge continental desert surrounded be mountains. Compare to the Tarim basin in China.
Why would this civilization go forward with this project to turn their Empire into an arid wasteland? Who wants more land area if it is like that, and comes at the cost of reducing the rainfall in the already productive parts of the empire? And why remove the wonderful internal lake (Mare Nostrum?) that provides everything from fish to beach holidays to cheap water transport? Building this dam would be suicidal.