Learn Icelandic: Hann mátar stóra stærð.

It describes the noun stærð (size), which is feminine. Since he is doing an action to the size, stærð is the direct object and takes the accusative case. For a feminine noun in the accusative case, the adjective stór changes to stóra.

If I want to ask "What size is he trying on?", how do I use hvaða here?

You would ask Hvaða stærð mátar hann? The question word hvaða (what/which) pairs right up with the noun it is asking about, just like in English. Then you follow it with the verb and the subject.

Does the verb máta mean to try anything, like trying food or trying to learn?

No, máta specifically means to try on clothing, shoes, or accessories to see if they fit. If you want to say you are trying or attempting an action, you use the verb reyna. If you are tasting food, you use smakka.

Did the word stærð change its ending because it is the object of the sentence?

No, it looks exactly like its dictionary form! Stærð is a feminine noun that happens to have the same form in both the nominative (subject) and accusative (object) cases. We only know it is accusative here because of the adjective stóra modifying it.