Combining Always Encrypted AND Column level encryption in SQL Server 2016
I have yet to come across a definitive "Best Practices" list regarding multiple encryption types for SQL Server, but in your situation I would probably recommend the following:


Encrypt necessary data using Always Encrypt


Its the new hotness. You're on 2016, enjoy it!
Better security - the DBA can't decrypt data since the key is stored outside the database. 
More options for tuning individual queries and reducing the performance hit of the feature. 
Easiest to implement on both the database and app side (unless TDE is an option) since you only have to configure driver parameters versus changing your queries as with Column Level Encryption. 
The additional decryption load becomes the application's (specifically the driver's) problem (fine for me as a DBA).
This feature is likely to be improved and optimized for a while since it is a new (my opinion). 

For columns you need to search on, create a hash value to do lookups on. 


Maintains security of the data but is very efficient for lookups. It allows you to have the performance of a searching on a normal row without the overhead of decrypting every row or defaulting to a table scan. You can index it for further performance if desired. 


Your app will take the user input and hash it, then use that hashed value to query the hashed version stored in the table. This lookup will be fast and will allow you to only decrypt the desired row(s) versus decrypting rows you don't actually want as part of your result set. 

Design of this depends on how many columns you need to look up and if you're using multiple or individual ones in your WHERE clauses.
Extra space is worth it for performance as long as you can afford it. 

Don't bother using Column Level Encryption


You'll have to decrypt the entire column to do searches, which will be less efficient than an un-encrypted hash column. This means the larger your table, the more inefficient this method becomes. 1 million rows means you have to spend the CPU to decrypt a million rows even if your filter is only returning 1 row. Just because you can perform a search doesn't mean it will be performant. 
I can see long term maintenance of two encryption features within the same table being confusing and becoming at best tribal knowledge. 



You can also implement #2 with Column Level Encryption as well, but without any constraints in place, I can't see why you'd choose CLE over Always Encrypted in general.

I joke about making encryption the application's problem, but I find that the database often gets saddled with a lot more business logic and wacky functionality than it should be in most cases. If there is an option to push some computation back to the application side, I've found that is generally the best option and helps prevent troubleshooting and general tuning from becoming a nightmare. 

Of course you should fully test the alternatives. If you find CLE, or a combo, works best for your particular scenario, so be it.



Additional reading:


Always Encrypted Performance - Aaron Bertrand
Always Encrypted Performance - A follow Up - Aaron Bertrand
Column Level Encryption Overhead - Dallas Snyder
Always Encrypted (Database Engine) (official documentation landing page)