It has nothing (or very, very little) to do with desalinization plants. It has to do with the balance between Evaporation minus Precipitation (E-P), rivers, and advection. The link to E-P is the main one:
Salinity is controlled by processes of concentration and dilution. Evaporation removes water vapor from the sea surface, but the salt remains resulting on an increase in salinity. Meanwhile, precipitation and river runoff flux into the ocean dilutes the salt resulting in lower surface salinities. Taking the difference between evaporation (E) and precipitation (P) provides the net gain or loss of water by the ocean.
Sea surface salinity (SSS) patterns are associated with general atmospheric circulation. The net air-sea freshwater fluxes and SSS have patterns that are remarkably similar (Baumgartner and Reichel, 1975; Durack and Wijffels, 2010). The ocean subtropical gyres are at edge of the atmospheric Hadley cells and result in SSS maxima in between 15 and 30 degrees latitude. Rain along the tropics associated with the Intertropical Convergence Zone results in lower SSS close to the Equator. North of the subtropical gyres and in the polar regions, excess precipitation also causes a drop in SSS. Also, there are differences between the Atlantic and Pacific oceans; with the Atlantic having more evaporation that causes a relatively saltier Atlantic basin.
The effect of rivers is extremely important on a local or even regional scale, but globally E-P dominates. Source: Woods Hole Oceanographic Institution
In the cases you mentioned, the Mediterranean Sea and Red Sea have a deficit of precipitation when compare to evaporation. Source: SMOS
Even though both of them are connected to the open ocean, the connections are limited (Straits of Gibraltar and Bab al-Mandab Strait) and the currents provide only limited volume exchange. The result is an increased in salinity over the basin especially away from the connection to the open-ocean (higher salinities around the eastern Mediterranean and northern Red Sea).
The area around the Bay of Bengal and Indonesia have both increased rain and river discharge resulting in lower salinities.
The water volume flux of the largest desalination plants is tiny when compared with the air-sea fluxes over an entire basin or the river discharge of large rivers. If you consider volume flux, the largest desalinization plant in the world (Ras Al Khair, Saudi Arabia) produces about 12 $m^3/s$. Meanwhile, the average river discharge of the Mississippi River is between 7,000–20,000 $m^3/s$. In the Mediterranean, river discharge, while smaller than the Mississippi, is still quite large.
Source: State of the Mediterranean Marine and Coastal Environment
Clearly, rivers around the Red Sea have way lower discharges. Another factor to consider is that the brine from desalinization plants is going to tend to sink deeper because of its higher density and it is going to not easily mix with the rest of the water column, not having a large effect on SSS. Ibrahim and Eltahir (2019) provides more info on the effect of desalination in the Red Sea.
Baumgartner, F. and Reichel, E., 1975. The World Water Balance: Mean Annual Global. Continental and Maritime Precipitation, Evaporation and Runoff (Ordenbourg, München, Germany, 1975).
Durack, P.J. and Wijffels, S.E., 2010. Fifty-year trends in global ocean salinities and their relationship to broad-scale warming. Journal of Climate, 23(16), pp.4342-4362.