Hi galapagos,
Unfortunately this is a fairly typical experience because the major brands (such as Sealy, Simmons, and Serta) tend to use lower quality and less durable materials in their mattresses that tend to soften and break down prematurely and this is the reason that I normally suggest to avoid them completely (see the guidelines here).
As you also unfortunately discovered … mattress warranties only cover manufacturing defects and they don’t cover the gradual (or more rapid in the case of lower quality comfort layers) loss of comfort and support that comes from foam softening that is the main reason that most people will need to replace their mattress. In other words the length of mattress warranties have little to nothing to do with the durability or useful life of a mattress or how long it will be until you need to buy a new mattress. If there is an actual defect in the materials it will usually show up early in the life of the mattress (usually in the first year or two) but knowing the quality/density and durability of the materials in your mattress is always a much more reliable way to assess the relative durability and useful life of a mattress than the length of a warranty. There is more about mattress warranties in post #174 here.
I would keep in mind that there will be a break in and adjustment period with any new mattress so I would wait a few weeks before making any changes or additions to your sleeping system (see post #3 here and post #2 here).
The type of material in a pillow is a preference choice rather than a better/worse choice and each person can have very different preferences. Some people may like the “feel” and response of a buckwheat pillow or a shredded latex pillow and some people may not like either one. In other words there isn’t a specific type of pillow material that is “better” than another one for any specific set of “symptoms”.
Having said that … every type of pillow will generally come in softer or firmer versions and thicker and thinner versions. Once you have decided on the type of pillow you prefer then it’s a matter of finding the softness and thickness that will keep your head and neck in good alignment in all your sleeping positions and this can be different for different people based on their body type, sleeping positions, and the type of mattress they are sleeping on (how much you sink into a mattress can affect the distance between your head and neck and the mattress). There isn’t a formula or “theory” that can be used to predict which specific pillow will work best for any particular person.
While I can’t make any specific pillow suggestions because this is such a personal choice with too many variables involved and I can’t feel what you feel on a pillow, see you sleeping on your mattress and pillow, or know whether a specific pillow keeps your head and neck in good alignment … in very general terms side sleepers need a loftier firmer pillow because the gap between their head and neck and their sleeping surface is larger, back sleepers need a little thinner pillow with some support under the neck, and stomach sleepers need the thinnest flattest pillow of all to keep their head as low as possible. Many people are combination sleepers and pillows that can be “scrunched” (feathers, down, shredded latex or shredded memory foam and many other materials) can help with this because they can be puffed up when needed on the side and flattened or molded when needed on the back or stomach.
Phoenix