How can a key lookup with zero executions and zero actual rows take time?
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.