How can a key lookup with zero executions and zero actual rows take time? I have a query that is taking about 10 seconds to run and I am trying to optimize it.

All the time is spent in the key lookup which is fine however in this case if I mouse over the key lookup in the actual execution plan it says

Expected Rows : 1
Estimated Executions : 3341
Actual Rows : 0
Executions : 0


I understand in this case the statistics are expecting the index seek to find rows which is fine but as no rows were returned in the Index Seek why would the key lookup take any time? or even be shown in the query plan at all?
The percentages on each operator that are shown in an "actual" plan are still estimates. The additions to an "actual" plan over "estimated" are the actual row counts and operator executes. 

In the example you've given the key lookup was estimated to be executed 3341 times, which is why it has a high estimated percentage cost.

One of the other operators is really consuming the time. Get a (free) copy of Plan Explorer from Sentry One, it'll make it easier to identify where.

If nothing stands out, start a new question and post the execution plan xml.