Well...
1. You may have seen some guide that said you unlock the word "Contest" by beating the E4 - also known as the Elite Four. Actually, I believe that is incorrect; I'm pretty sure that all you have to do is get a Contest Pass. You can get one by entering a Contest Hall and requesting one at the main desk. (This key item will also allow you to enter contests. Yay!)
2. For evolution, it's not enough to max out the Feebas' Beauty and then let it sit there. You can check with the Pokemon Fan Club Chairman in Slateport city to see if its Beauty has been maxed out. If it has, all you need to do is train it until it levels up (or just give it a Rare Candy), and it will evolve. But its Beauty must be maximized first! Also, if its Beauty is maximized, you don't get any bonus for trying to increase it further, so you'll just be wasting your Pokeblocks. If you think that its Beauty may have reached its peak, check with the Fan Club Chairman.
I hope that helps.
EDIT: By the way, there's a much easier way to get some Kelpsy berries. You can grab six of them on route 115 and then replant and water them to get a heck of a lot more. Be warned, though, that the stash of six can only be grabbed once. If you use all of those, then you'll have to get the only other one from the Berry Master's wife. And if that's the case, then be sure to plant them, water them, and repeat many, many times. Otherwise, you'll likely never be able to get any more Kelpsy berries (without taking the time to trade one over from another cartridge, or something along those lines).