Would it be easy/possible given that the IO line needs to be bi-directional?
Possible? Yes. Easy? Not so. You would have to detect the direction within the CPLD and switch the pins between input and output accordingly. It is a lot easier to just use an analog multiplexer chip like the 74HC4051 and control the address bits from a CPLD or microprocessor.
Would the propagation delay of the CLK be an issue at all?
In practice there is no phase relationship between CLK and IO, so it is not an issue. CLK is only used to define the baud rate of the IO line and runs at a much higher speed than the duration on a bit over the IO line. The initial speed of the IO line is one bit per 372 clock ticks. Your GSM modem may negotiate a higher speed transfer later on but lag on the CLK will never be a problem.
Anything else that might prevent this from working?
If you want to switch the VCC of the SIM cards via the CPLD check the maximum current that the CPLD can drive. You may need an additional driver to provide enough power.
I don't have any experience with CPLDs
A good opportunity to start lerning how to use them. They're fun!
On the other hand if you want to finish your project fast it is probably easier to just use four analog multiplexers like the 74HC4051 and switch all signals in parallel from a microprocessor. All you need are 3 GPIO pins to control up to 8 SIM cards. You won't have to deal with different voltage levels that way either.
Oh, one last thing: In practice all SIM cards nowadays support 1.8V and 3V so you don't really have to follow the power up sequence of starting with 1.8V and then switching up to higher voltages. For a commercial project I would not recommend this, but for a hobby project I think it's fine to simplify here.