Should I add multiple secondary indexes to search
It really depends.  If as in your example the users do a search for just the firstname and country then the index will be used.  Let's say your user does a search by zip.  At that point SQL may do a scan on your index (generally faster than a table scan) but an index starting with ZIP would be much faster.  

The problem is every index you add increases your write time.  Generally adding indexes is a balancing act between the increased write time caused by an additional index and the benefit of the index on reads.  If for example this is a table where there are tons of writes all the time you may want to be careful with your indexes.  If on the other hand it's a read only table then you can be less careful.

I recently added a very large index to a table on a query that is only being run once a day.  However that particular query is very important to my business and HAD to go faster.  So the additional cost of the index wasn't as important as the increased speed of the query.

If I had to guess from your question I would say that this search is going to be run frequently.  Given that this is your only index on the table you might add additional indexes with LastName first and another with Zip first.  Initially I wouldn't bother with an index starting with CountryCd because it isn't going to be all that selective and so probably not as useful. If on the other hand you find users querying on CountryCd alone frequently then you may have to add it later.

After your system has been running with the new indexes for a bit then you should check the sys.dm_db_index_usage_stats DMO to confirm that the index are in fact being used.