However, when you use the wheel to select where the Castillo Caballeros go, can it be any region on the board or just those surrounding the king?
The rules just say choose a region. You can pick any region except the King's region. The only time you have to place adjacent to the king is when you place Caballeros on the board using your action card.
Also, if you use an Intrigue card like "You may move 2 of your Caballeros and 2 foreign Caballeros" from the picture it looks like they have to be adjoining regions, but does one have to have the king in it?
You can move them to any region or the Castillo. See Action Card Clarifications on the top of page 9.