Store this data model as non-relational?

Solution 1:

Or do you have some completely different ideas?

You can do better with a better set of index designs. You want to optimize for your most expensive queries:

SELECT *
FROM myTable 
WHERE Fk1 = 123456 AND FK2 = 654321 
-- works badly because it gets 100.000 - 300.000 records but I need all of them. Yes, unique index is used because order of index is correct )

UPDATE myTable 
SET Value1 = '1', Value2 = '2', Value3 = '3', Value 4 = '4', 
    Value5 = '5', Value6 = '6', Value7 = '7', Value8 = '8' 
WHERE Fk1 = 123456 AND FK2 = 654321 

Making FK1_FK2_FK3 the clustered index and making ID a non-clustered PK would be better. For queries that retrieve a handful of rows, using nested loop join from the non-clustered PK to the composite clustered index should be fine. But doing 300,000 lookups when querying by (Fk1,Fk2) is going to be expensive. It's so expensive that these queries might be doing table scans instead.

And after clustering the table by (FK1,FK2,FK3) consider partitioning it by FK2 into 10-100 separate partitions. Then a predicate like WHERE Fk1 = 123456 AND FK2 = 654321 will only have to scan the partition containing FK2=654321, and can seek in that partition directly to the first page with FK1=123456.

In addition consider ROW or PAGE compression if PAGEIOLATCH waits are a significant part of your query runtime.