The Hedonism paradox suggests that one attempting to obtain happiness through pleasure will never meet their goal. It does not suggest that the road to happiness isn't with pleasure, merely that one searching for happiness will never find the way.
Feeling happy is not the same thing as being happy. One is a fleeting emotion, the other a state of being. It can be argued what exactly that means, but to me it implies some stability. A person suffering from depression may be happy while riding a rollercoaster, but it is unlikely to lead to a lasting state of happiness.
I do not like to take things straight from wikipedia, but in this case I'm going to make an exception. The following example is excellent.
Suppose Paul likes to collect stamps. According to most models of behavior, including not only utilitarianism, but most economic, psychological and social conceptions of behavior, it is believed that Paul collects stamps because he gets pleasure from it. Stamp collecting is an avenue towards acquiring pleasure. However, if you tell Paul this, he will likely disagree. He does get pleasure from collecting stamps, but this is not the process that explains why he collects stamps. It is not as though he says, "I must collect stamps so I, Paul, can obtain pleasure". Collecting stamps is not just a means toward pleasure. He simply likes collecting stamps, therefore acquiring pleasure indirectly.
This paradox is often spun around backwards, to illustrate that pleasure and happiness cannot be reverse-engineered. If for example you heard that collecting stamps was very pleasurable, and began a stamp collection as a means towards this happiness, it would inevitably be in vain. To achieve happiness, you must not seek happiness directly, you must strangely motivate yourself towards things unrelated to happiness, like the collection of stamps.[1]
To achieve a life of happiness it is important not to make that your goal. There are many things in this world that will derive temporary pleasure, but only a few that will give you a lasting state of happiness. So go out and find the things that truly interest you, they may be frustrating at times, but that is the path to true happiness.