I can think of three solutions - EAV, XML, and Sparse Columns. The latter is vendor-specific and may not be useful to you.
Whichever method you choose, you may wish to consider storing the original request data in a raw format, in a table or flat file. It will make it easy to try new ways of storing the data, allow you to reload data if you discover a mistake with the way you're parsing your requests, and offer opportunities for parsing the API requests using batch processing or "big data" tools if you find that your data warehouse isn't able to efficiently deal with the data.
EAV considerations
EAV/KVS, as you've described it above, is likely to be the most straightforward implementation.
Unfortunately it's also going to be very expensive - to get any sort of efficient queries on commonly used keys you'll need to have indexes on the key column, which could get very fragmented. Querying for particular keys would be extremely expensive.
You may be able to reduce the cost of indexing or index scans by supporting your EAV store with materialised views (many vendors support this) for querying keys or values that you care about.
XML
Most enterprise database systems offer very mature XML handling, including validation, indexing, and sophisticated querying.
Loading the API request into the database as XML would provide one tuple per request, which logically might be a bit more palatable to you than having an unknown number of rows in an EAV table.
Whether this is efficient would depend a lot on your RDBMS vendor and your implementation.
The biggest downside is that this is probably the only way of managing data that's more complicated than string manipulation of the original request!
Sparse Columns / traditional tables
It's possible that you could load your data into a traditional table structure, with one column per key.
SQL Server's Sparse Columns feature is a great alternative to an EAV store. A table with Sparse Columns behaves much the same as a normal table, except that it can have up to 30,000 columns, and NULL values in sparse columns consume no space in the table.
Combining them with Filtered Indexes (another SQL Server specific feature) can provide an extremely efficient alternative to an EAV store if you're frequently querying for a couple of specific columns and/or values.
Using a traditional table with other vendors may be viable - IBM supports over 700 columns per table and Oracle about 1000, and features such as compression or Oracle's treatment of trailing nulls might mean that you can store your API data fairly efficiently.
The obvious downside of this approach is that as you added new keys to your API, you'd need to adjust your schema accordingly.
Best Answer
Almost always surrogate keys (your "Auto Incrementing primary key") are best in data warehouses. I have seen very few exceptions where this is not the case (but some do exist) - yours does not seem to be exceptional. To answer why would be repeating stuff you can find all around the web, by the giants in the field, for instance: http://www.kimballgroup.com/1998/05/surrogate-keys/