The only problem with using A* is finding an admissible heuristic for your problem. Fortunately, this has already been answered here.
How would the system identify areas that need teleporters?
That depends on where the turtle is actually moving to/from. If he's always moving to/from the same start/end points, the answer is trivial: add teleports at the start and finish. For more complicated setups, my guess would be that this is NP-hard; if true, you'll have to look into global-optimization strategies (or just try a bunch of random positions and take the best one).