沖縄発なら...

関空経由でルフトハンザ航空でフランクフルトへ行くのがよいと思います。ANAと連携しているので乗継が楽で，フランクフルトまで直行です。小さなお子様をお連れなら，これがよいでしょう。Skyscannerで検索すると，もっと安いのがありますが...
http://www.skyscanner.jp/

バルセロナは別の機会にされては？