Yes, the spell speak with animals does allow you to speak with animals, including a seagull. It doesn’t have any specific interaction with wild empathy or Handle Animal, but each of those can be used to make the seagull more friendly towards you and more inclined to help you.
Exactly what it takes to get a seagull’s attention and willingness to honestly answer questions is up to the DM. Your Handle Animal modifier is very high, but Handle Animal is for trained, domesticated animals—or for taming and training a wild animal. The latter, though, has to be something you’ve done with that animal since its birth; for a wild seagull you find in, ya know, the wilds, it doesn’t really apply. Wild empathy would be more appropriate in this situation, and that’s the check I would ask you to make as GM, personally.
On the other hand, my experience with seagulls is that they are curious, and more than a bit brazen—not exactly skittish animals. That may be specific to the seagulls found in areas frequented by humans, in the modern world where humans rarely—if ever—attack them, and often provide food. In the world of D&D, seagulls might be more skittish. But I suspect they would still be curious—and very, very interested in any bribes (food) you have to offer. Ultimately, I wouldn’t make it a very difficult wild empathy check to talk to a seagull, particularly if you were offering food.