I believe migratory birds will sometimes fly to what seems like an absurdly high altitude over land, before setting out across water (probably both to exploit thermals, and just for general prudence.
Bird strikes on aircraft are common at and above 5000 feet altitude, so birds definitely go that high - and a gull would be little more than a speck at that distance, to the naked eye.