One for the Morning Glory - John Barnes. Top of my list. Action, adventure, a prince who has lost half of his body, and Highly Unpleasant Things It Is Sometimes Useful To Know.
The Face in the Frost - John Bellairs. Up there with A Wizard of Earthsea for good takes on wizards, and less likely to be found in the course of everyday life.
Speaking of Ursula LeGuin, the first three Earthsea books are a good plan, and I highly recommend Very Far Away from Anywhere Else.
The Phantom Tollbooth - Norton Juster, if she hasn't read it yet, and if the illustrations work correctly on the Kindle.
Has she read The Westing Game - Ellen Raskin? That one's probably in her school library.
Oh, and of course for introductions to SF for someone who likes mysteries, try The Caves of Steel - Asimov.
A Wrinkle in Time and sequels by Madeline L'Engle.
The Caves of Steel by Isaac Asimov. (You said she likes mysteries, right?)
Fablehaven by Brandon Mull.
Anything Tamora Pierce; I'm partial to the Circle of Magic but you could start her in Tortall just as well.
His Dark Materials by Philip Pullman.
Enchanted Forest Chronicles by Patricia C. Wrede.
Ella Enchanted by Gail Carson Levine.
Sophie's World by Jostein Gaarder
Sharon Shinn (not arbitrary books, some of them have a touch of adult content, particularly avoid Wrapt in Crystal and Heart of Gold until she's a bit older; I recommend Archangel in another comment and that's a fine starting point but I think Safe-Keeper's Secret and seq...
Be careful - if you try too hard to change her opinions, she might decide Sci-Fi is no good at all. Try to cater to what you know about her interests.
The Scott Westerfeld "Uglies/Pretties" series might be a good introductory book for a girl who isn't interested in sci-fi yet. It has some interesting dystopian implications, but doesn't obviously have the "ALIENS! SPACE!" aesthetic overtones of most sci-fi, which is what turned me off from sci-fi books as a kid.
(I was also mostly into YA fantasy, and didn't like sci-fi until I discovered the part of it that was really about philosophical and ethical questions, not just aliens and space.)
Has she read The Phantom Tollbooth? That's definitely one that's worth checking out. I can never remember what books are at what reading level, but I'm pretty sure it's age appropriate.
Honestly, I've never had a taste for most sci fi either, I've always found it much harder on my suspension of disbelief than fantasy. It's one thing for me to accept a setting that runs on fundamentally different rules, but when a story that's nominally set in our own universe differs from our own in implausible-seeming ways, my instinct is to call bullshit. Sci fi scenario...
Within YA mysteries, my favorites as a child were The Three Investigators. They had more clever plots than the Hardy Boys and other series, and the protagonists did more actual deduction, observation and reasoning. Also, cameo appearances by Alfred Hitchcock! Sadly, they don't seem to be available for Kindle.
If she hasn't read it yet, you could give her Sherlock Holmes. Quite a lot of (19th century, but still) science and methodic reasoning, should be read before other classical mystery authors like Agatha Christie (because all were reacting to it), and wi...
Even as an adult, I enjoyed The Mysterious Benedict Society books by Trenton Lee Stewart. 4th/5th grade is probably about right. How can you not love a series with a book titled The Mysterious Benedict Society and the Prisoner's Dilemma?
I loved these books as an early teen:
Fantasy: The Hobbit (Film coming out in a few months). No hidden pro-science virtues but a lovely, funny book.
Adventure stories:
Since you said she's interested in fantasy, I'd suggest the Enchanted Forest Chronicles by Patricia C. Wrede (Dealing with Dragons is book one.) Unfortunately it's not on the Kindle yet, but it does a good job of pointing out common fantasy tropes in an entertaining way. Also, the main female character is a very good role model.
If you want more of a scientific mindset applied to fantasy, I'd say The Last of the Really Great Whangdoodles by Julie Andrews Edwards instills scientific curiosity very well. Also not available on Kindle...
Finally, (this time a...
I remember enjoying the Prydain Chronicles by Lloyd Alexander when I was at that reading level. It's a lot like Lord of the Rings for children. A Series of Unfortunate Events by Lemony Snicket, Detectives in Togas by Henry Winterfeld.
For sci fi for about that age, maybe Interstellar Pig, although it does not seem to be available on Kindle. Might be a little scary (scared me when I was about that age). Caveat - haven't read it since I was a kid, so not sure how well it holds up.
How about an anti-birth control story where the third child (In a world where like, you know, only 2 children are normally allowed) becomes trapped naked in a bathroom with a mean bully, so he brutally murders him to escape... then goes on to commit widespread genocide. Young girls love that stuff.
Oh wait, Ender's Game is already on your list. Oops.
Snow Queen by Joan D. Vinge, which won a Hugo Award, is by far the clearest example and best suggestion I can think of, but I'm not seeing it on the Amazon Kindle market. Shucks, what I get for trying to be witty.
The Giver trilogy is age appropriate and well-written dystopian children's novel. I remember very distinctly that this was my first exposure to what seemed like a plausible future world. (I read this in 4th grade so it might be too easy. )
The Hitchhiker's Guide to the Galaxy would also be good; I read this in 6th grade and it was book that sparked my interest in sci-fi.
Smith of Wootton Major . I read this book when I was about 10 or 11, and I still remember what it felt like as it rewired my mind.
Ender's Game, of course, as you'd said.
Scott Westerfeld's Leviathan trilogy (not to be confused with that other book by the same title).
Pretty much anything by Terry Pratchett except for The Colour of Magic (it's not great), but especially the Tiffany Aching books (starting with The Wee Free Men), and possibly Small Gods.
Neil Gaiman's Stardust, and especially The Dream Hunters.
The Myth series by Robert Asprin.
Hmm, upon reflect...
The Artemis Fowl series should spur an interest in technology - I loved it (I only read up to The Eternity Cube though). The plans in the series also have a lot of flaws, that were frustrating to notice, but I suppose that could provide some lesson or another. It's pretty irrational actually; I suggest it as it may provoke a reaction to irrationality.
Little Brother by Cory Doctorow. It made me really want to learn programming, thought I'm not sure what reading level it is.
The Great Book of Amber by Roger Zelazny should be right up her alley in a couple years.
I bought my niece a Kindle that just arrived and I'm about to load it up with books to give it to her tomorrow for her birthday. I've decided to be a sneaky uncle and include good books that can teach better abilities to think or at least to consider science cool and interesting. She is currently in the 4th Grade with 5th coming after the Summer.
She reads basically at her own grade level so while I'm open to stuffing the Kindle with books to be read when she's ready, I'd like to focus on giving her books she can read now. Ender's Game will be on there most likely. Game of Thrones will not.
What books would you give a youngling? Her interests currently trend toward the young mystery section, Hardy Boys and the like, but in my experience she is very open to trying new books with particular interest in YA fantasy but not much interest in Sci Fi (if I'm doing any other optimizing this year, I'll try to change her opinion on Sci Fi).