If it is a simple html based form, it can be easily filled with cURL
I'm not clear what you mean here. As far as I know, cURL is a tool for making HTTP requests. It can't "fill forms" (unlike, for example, WWW::Mechanize). Am I wrong about this?
I think you mean: "If it is a simple HTML based form, I can easily construct an HTTP request using cURL that submits the same query string or POST data as using a browser would." I'm going to proceed on that assumption.
The use of Ajax (in of itself) doesn't stop you constructing a the form data manually and submitting it as normal. It just makes it a little more difficult to work out what data you need to submit.
The remote system might be implemented in such a way that it falls over if you don't request all the bits of data in the right sequence (e.g. it will barf if you submit the complete data at the end without requesting the list of cities for a country). Emphasis on 'might', this wouldn't be a sane way to implement the system.
You might also want to make multiple requests with cURL anyway so that you can fetch the list of cities (and any ids that might be associated with them) and access them programatically.