Should I add page level compression before adding the primary key, or after?
The clustered index is in fact the table.  On the assumption that your primary key is clustered then I would create a clustered primary key with page level compression rather than trying to do it in two steps.

-- Add primary key
ALTER TABLE             dbo.TableName
ADD CONSTRAINT          PK_TableName
PRIMARY KEY CLUSTERED   (&lt;Columns&gt;)
WITH (DATA_COMPRESSION = PAGE)
;


I would also copy about 100k rows to a temporary (temporary physical not #temporary) table and run some tests.  Try running compression first, clustered key first, try doing them as one step.  See what runs fastest.  I would guess it will be one step personally :).