War between revolutionary Spain and Hejaz? The good ol' Paradox weirdness is finally kicking in, after a quite historical game . I find trying to cover such things to be one of the hardest things while writing an AAR (a CK game with the king of Léon being king of Ireland too, in 1080!).
As for which part of Spain to go for: my choice would either be (a part of) the Philippines or Puerto Rico. Keeping your colonies somewhat grouped makesthem easier to govern and defend.