CPU vs Elapsed & Parallelism
Your first query plan shows parallelism, whereas your second query is purely serial; this is why the second version is showing longer "duration".  

The key lookup operations could be prevented by a suitable covering index for the tables where the key lookup is occurring.  The standard warning about not blindly creating indexes applies here - don't create duplicate indexes, and check to see if you can leverage an existing index by possibly adding an include clause.  For instance, the key lookup on the Customers table is pulling these columns, which it couldn't get by scanning the IX_CustomersSocialSecurityNumber index:

[GoOutdoorsTN_TEST].[dbo].[Customers].driversLicenseNumber
, [GoOutdoorsTN_TEST].[dbo].[Customers].lastName
, [GoOutdoorsTN_TEST].[dbo].[Customers].DocTypeNumber
, [GoOutdoorsTN_TEST].[dbo].[Customers].driversLicenseState


If you added those columns to the index in an INCLUDE clause, that scan would not need to go back to the table to get those columns, making the output that much faster.

Your query uses the "kitchen sink" pattern; i.e. this:

WHERE (@x IS NULL OR someCol = @x)
     AND (@y IS NULL OR someOtherCol = @y)


You can typically get much better query plans, customized for each variation, using dynamic SQL instead of the @x IS NULL piece.  Pseudo-code would be:

IF @x IS NULL AND @y IS NOT NULL
    SET @where = 'WHERE someOtherCol = @y';
IF @y IS NULL AND @x IS NOT NULL
    SET @where = 'WHERE someCol = @x';
IF @y IS NULL AND @x IS NULL
    SET @where = '';


This allows the query optimizer to use column statistics in a far more effective manner, since it only needs to think about the columns presented in each unique where clause.

Also of note, I see you're using WITH (NOLOCK) in an effort to prevent your query being affected by blocking.  You may want to ensure you understand the effects of reading uncommitted rows inherent in the READ UNCOMMITTED isolation level used by the NOLOCK hint.  Aaron Bertrand has a great article about that here

I've noticed the plans show a couple of computer scalar operators where you're doing:

= LTRIM(RTRIM(lastName))


Does your data really have blank space around the real content of lastName?  If not, getting rid of those needless functions will really help the query processor provide better plans.

As a way of showing how you might approach the kitchen sink problem, and strictly for learning purposes, consider the below code.

CREATE TABLE dbo.Customers
(
    CustomerID int NOT NULL
        CONSTRAINT PK_Customers
        PRIMARY KEY CLUSTERED
        IDENTITY(1,1)
    , FirstName nvarchar(100) NOT NULL
    , LastName nvarchar(100) NOT NULL
    , SSN char(9) NULL
);


Some sample data:

INSERT INTO dbo.Customers (FirstName, LastName, SSN)
VALUES ('Joe', 'Belfiore', '012345678')
    , ('Bill', 'Gates', '876543210')
    , ('Max', 'Vernon', '123123123');
GO


A stored procedure to perform searches:

CREATE PROCEDURE dbo.SearchCustomers
(
    @FirstName nvarchar(100) = NULL
    , @LastName nvarchar(100) = NULL
    , @SSN varchar(9) = NULL
)
AS
BEGIN
    /*
        BE AWARE THIS IS PROTOTYPE CODE THAT IS NOT SAFE
        AGAINST SQL INJECTION VULNERABILIES.

        IT IS STRICTLY TO SHOW HOW TO COMPILE A DYNAMIC
        WHERE CLAUSE!
    */
    SET NOCOUNT ON;
    DECLARE @Where nvarchar(max);
    DECLARE @connector nvarchar(max);
    DECLARE @qry nvarchar(max);
    SET @qry = 'SELECT CustomerID, FirstName, LastName, SSN
FROM dbo.Customers c
';
    SET @where = 'WHERE ';
    SET @connector = '';
    IF @LastName IS NOT NULL
    BEGIN
        SET @where = @where + @connector + 'c.LastName LIKE ''%' + @LastName + '%''';
        SET @connector = ' AND ';
    END
    IF @FirstName IS NOT NULL
    BEGIN
        SET @where = @where + @connector + 'c.FirstName LIKE ''%' + @FirstName + '%''';
        SET @connector = ' AND ';
    END
    IF @SSN IS NOT NULL
    BEGIN
        SET @where = @where + @connector + 'c.SSN LIKE ''%' + @SSN + '%''';
        SET @connector = ' AND ';
    END
    IF @connector &lt;&gt; '' SET @qry = @qry + @Where + ';';
    EXEC sys.sp_executesql @qry;
    PRINT @qry;
END
GO


Some test searches:

EXEC dbo.SearchCustomers @FirstName = N'Max';
EXEC dbo.SearchCustomers @LastName = N'Vernon';
EXEC dbo.SearchCustomers @SSN = N'994', @LastName = N'V'


The queries show in the "Messages" tab are:

SELECT CustomerID, FirstName, LastName, SSN
    FROM dbo.Customers c
    WHERE c.FirstName LIKE '%Max%';

SELECT CustomerID, FirstName, LastName, SSN
    FROM dbo.Customers c
    WHERE c.LastName LIKE '%Vernon%';

SELECT CustomerID, FirstName, LastName, SSN
    FROM dbo.Customers c
    WHERE c.LastName LIKE '%V%' AND c.SSN LIKE '%994%';


Before you implement that code, you really need to read Erland Sommarskog's seminal work on dynamic SQL.  He also has a great article about dynamic search which should help.