Note you should not need to use the Southwest tickets as any of the programs should include necessary domestic flights (although it is possible sometimes you have to accept economy on the domestic legs if first/business is not available, but that isn't a big deal).

TK may also be an option with Star (*A).

Besides *A, Delta (Skyteam) has Air France and KLM as partners who serve CAI. Since Delta miles are notoriously hard to get anything decent from, if you can find an itinerary for 120,000 miles in business (I think that is the lowest regular level), you might want to grab that and save your other miles, which are more valuable. I saw availability on random dates I checked. Be cautious about (1) very long or very short layovers (2) extra stops and (3) some itineraries or dates that require a lot of "extra" miles.

On American, you can use British Airways or Royal Jordanian to reach CAI. I think AA requires more miles and doesn't have partner search online so I don't know about availability but you can call and get an idea.