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 find it doubtful that C. S. Lewis ever intended it to be convincing. He wanted it to function as a fantasy story, but I think he also wanted it to resonate with people who buy into the Christian myth, and to make people who don't think "Huh, so this thrilling fantasy story is something that all ties into Christian belief? I'd be interested in learning more about that then."
When I realized what it was supposed to be an allegory for, though, I was hit by a wave of plot elements I'd always accepted as perfectly sensible fantasy elements which suddenly struck me as crashingly wrong. It was like Hirou's revelation in The Sword of Good. Like when, just a few chapters earlier (I was rereading Prince Caspian, at the part where Aslan tells Peter and Susan that they won't be able to return to Narnia and would have to come to know him in their own world, and it finally hit me that he was supposed to be Jesus,) Lucy had asked Aslan why he couldn't simply raise up an army and crush Miraz like he did with the White Witch, and Aslan said something like "Child, don't you know such things are never done the same way twice?" I wanted to shout at him, "Why!? Justify yourself to me, Aslan!" The bottom dropped out of the plot and everything started to seem arbitrary and unnecessary; Aslan has the power to solve every problem, he has absolutely no need for the protagonists, has no comprehensible reason for selecting them out of the entire world population to fill their spots in the song and dance he's orchestrated, and the entire structure of the plot is determined by some set of supernatural laws or requirements which are completely opaque to the reader.
C. S. Lewis wrote that an allegory should be able to stand on its own merits as a narrative, but once I turned a more critical eye to it, I was overwhelmed by the degree to which the Chronicles of Narnia failed to do so. The grand structure of the plot rests entirely on authorial fiat, rather than any comprehensible chain of cause and effect. The offensiveness of some of the story elements (such as the Calormenes almost all being unwitting devil worshipers,) was overshadowed by the pointlessness of it all.
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).