Query runs slowly when a non-indexed column is added to the WHERE clause
You're getting a secondary predicate on the key lookup operation. That's going to slow stuff down. It's not doing a full scan, but remember that even seeks are just limited scans. So the key lookup is still doing what it did before, but now it's also adding a filtering step because of that added index. 

You could look at exploring a covering index, however, because you have a SELECT *, covering means all columns, effectively creating a second clustered index. There'll be some sacrifice of performance on data modification queries and on disk space (depending on where you are on Azure SQL Database, that could bump you to another tier).

Instead, I'd start with experimenting with your existing nonclustered index. See if adding this new column to the key of that index helps at all. Keep it as the second column, other wise you're changing your histogram which could cause other issues.

You're going to have to experiment to see for sure what works best in your situation.