Sql-server – Reducing deadlocks with update query hint or other method

I'm getting 20-30 deadlocks per day on the same table. (2 mil rows)
Profiler DeadlockGraphs show KEY LOCK and PAGE LOCK (See attched jpg)
Total datatype size per row = 114 bytes

We have multiple departments that run a process that takes orders from our PreOrders table,
checks the rows and inserts them into the actual orders table.
This very import process is VB6. So to illistrate I simplified it in TSQL (Below).

The first SELECT statement is the deadlock victim and the end UPDATE statement is the winner. (Different SPIDs)
There are 4 different departments, each running this process every 30 secs.

After reading several articles, I was thinking my easiest option would be to add WITH (ROWLOCK) to the update statement.
I am able to recreate this entire process in TSQL, except for the automatic printing of invalid rows.

What other options do I have?
This'll be the first time I've had to use a query hint and am a bit reluctant as my knownledge on hints is (still) limited.

--Loop through headers 
-- THIS SELECT STATEMENT IS ALWAYS THE DEADLOCK VICTIM
SELECT  PreOrderID, <Other columns....> 
FROM    PreOrders PO -- 2 mil rows
        INNER JOIN Customers C -- 50 K rows
            ON PO.CustomerNr = C.CustomerNr
WHERE   Processed = 0 
        AND Department = 4 -- This is also the account number related to the Deadlock process

BEGIN
    -- < 100 orders

    -- Loop through rows
    SELECT  ProductNr, Amount, Price, <Other columns....> 
    FROM    PreOrders 
    WHERE   PreOrderID = @PreOrderID

    BEGIN
            -- AVG 9 rows per order

            -- Get data to validate the order row with
            SELECT  Availibilty, Price, isActive <Other columns....> 
            FROM    Products P -- 100 K rows 
                    LEFT JOIN ProductLocations PL -- 35 K rows
                        ON P.ProductNr = PL.ProductNr
            WHERE   P.ProductNr = @ProductNr
            -- Validate the order rows against the actual product data
            -- Bad rows get emailed and insert with a counter row (Cancels the row order)
            -- Good rows get inserted into actual Orders table
    END

    -- Generate the new order number
    -- Save the head and rows into the acutal order tables
    -- Update the preOrder as having been processed

    -- THIS UPDATE STATEMENT IS ALWAYS THE DEADLOCK WINNER
    UPDATE  PreOrders -- !!*** WITH (ROWLOCK)
    SET     Ordernumbers= @OrderNumber, -- Newly generated number)
            Processed   = 1
    WHERE   PreOrderID  = @PreOrderID

BEGIN

EDIT: Added screenshots