Thanks for the question.
I don't have any experience with Rails, but I can throw in my two cents:
I recommend doing such a thing in pieces. Move parts of your service into Clojure that are easily separated out, one at a time.
I think you're onto something there. I'm not sure how devise works, but regular HTTP cookies + sessions are possible in Clojure.
I've used SQS and it's a decent service with a simple API. But I wonder if you need background jobs. Remember, the JVM has a lot of nice threading model. Often a move to the JVM allows you to get by without an external queue. Evaluate how many jobs you really need, or whether the sidekiq queue is used as a communication mechanism between servers.
Heroku is entirely possible for Clojure and a solution I prefer. I've also used Elastic Beanstalk. And of course EC2 is ok. Am an not familiar with the other computing services on AWS.
I just want to reiterate that you do one piece at a time! Otherwise you're doing a big rewrite.
I hope that helps.