Faits:
A.
Par jugement du 26 mai 2011, le Tribunal correctionnel du canton de Genève a reconnu X._ coupable d'actes d'ordre sexuel avec des enfants, de contrainte sexuelle et de viol. Il l'a condamné à une peine privative de liberté de six ans et demi, sous déduction de la détention avant jugement.
Par arrêt du 14 novembre 2011, la Chambre pénale d'appel et de révision de la Cour de justice du canton de Genève a estimé que l'appel formé par X._ était réputé retiré (art. 407 al. 1 let. a CPP), ce dernier ayant fait défaut à l'audience d'appel. Par arrêt 6B_37/2012 du 1 er novembre 2012, le Tribunal fédéral a infirmé cette appréciation, annulé l'arrêt du 14 novembre 2011 et renvoyé la cause à l'autorité cantonale pour nouvelle décision. Par arrêt du 18 décembre 2012, la Chambre pénale d'appel et de révision a annulé le jugement du 26 mai 2011. Statuant à nouveau, elle a dit que l'action pénale était prescrite s'agissant des faits commis, selon l'acte d'accusation, entre mai et août 2006 à Rome et que la peine privative de liberté à laquelle était condamné X._ était fixée à six ans. Elle a pour le surplus repris le dispositif du jugement du 26 mai 2011. Par arrêt 6B_225/2013 du 8 juillet 2013, le Tribunal fédéral a rejeté dans la mesure de sa recevabilité le recours interjeté par X._.
B.
B.a. Le 13 mars 2013, le Ministère public a émis, à l'attention du Service de l'application des peines et mesures genevois (ci-après : SAPEM), un écrou judiciaire à l'encontre de X._, fondé sur l'arrêt de la Chambre pénale d'appel et de révision du 18 décembre 2012. A la suite d'une première convocation annulée, le SAPEM a convoqué X._ pour le 27 septembre 2013. Selon celui-ci, il a, à cette occasion, exprimé le souhait de pouvoir passer Noël 2013 avec son épouse et ses deux enfants. Il a été décidé que l'entrée en détention s'effectuerait en février 2014 au pénitencier de Witzwil. Par courrier du 30 septembre 2013, le SAPEM a sollicité dudit pénitencier, "si c'était possible", la réservation d'une place en section ouverte pour le 10 février 2014.
B.b. Le 12 septembre 2013, une socio-thérapeute de l'établissement La Pâquerette a été tuée, l'accusé dans cette affaire étant un violeur récidiviste, qui y purgeait sa peine, et qu'elle avait accompagné lors d'une sortie autorisée.
Dans ces circonstances particulières, le Conseiller d'Etat genevois en charge du Département de la sécurité a personnellement donné pour instruction au SAPEM de procéder à un nouvel examen du dossier de chaque personne condamnée à raison d'une des infractions listées à l'art. 64 al. 1 et 1 bis CP. C'est à la suite de cet examen que le cas de X._ lui a été signalé. En sa qualité de Chef du Département dont dépendait le SAPEM, il a alors donné des instructions orales, à la suite de quoi la directrice de ce service a délivré un ordre d'écrou le 4 octobre 2013.
B.c. Le 4 octobre 2013, X._ a été arrêté par la police genevoise à son domicile et conduit à la prison de Champ-Dollon. Le même jour, le SAPEM a transmis à la direction de la prison de Champ-Dollon un ordre d'écrou.
C.
X._ a recouru contre la décision d'incarcération prise par le Département de la sécurité et contre l'ordre d'écrou du SAPEM. Par arrêt du 17 décembre 2013, la Chambre pénale de recours de la Cour de justice du canton de Genève a rejeté le recours.
D.
X._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt du 17 décembre 2013. Il conclut, avec suite de dépens, à ce que l'illégalité de la décision d'incarcération et de l'ordre d'écrou soit constatée et à ce que sa libération immédiate soit ordonnée.

Considérant en droit:
1.
Le recours en matière pénale est ouvert contre les décisions relatives à l'exécution de peines et de mesures (art. 78 al. 2 let. b LTF).
2.
On peut se demander quel intérêt juridique et actuel (cf. art. 81 al. 1 let. b LTF) le recourant conserve à son recours. Il ne conteste pas devoir purger sa peine et l'hypothèse de passer les fêtes de Noël 2013 en famille n'a plus de portée. Une libération n'apparaît ainsi pas susceptible d'entrer en ligne de compte. Il n'expose pas non plus sur quelle base légale il peut prétendre obtenir une constatation de la prétendue illicéité de l'incarcération. La question de la qualité pour recourir selon l'art. 81 LTF peut cependant rester ouverte, vu le sort du recours.
3.
Se plaignant d'une application arbitraire de l'art. 5 du règlement genevois sur l'organisation de l'administration cantonale (ROAC/GE; RSG B 4 05.10), de l'art. 5 al. 2 let. d et g, et al. 5, ainsi que de l'art. 40 al. 2 let. a et al. 3 de la loi genevoise d'application du code pénal suisse et d'autres lois fédérales en matière pénale (LaCP/GE; RSG E 4 10), le recourant soutient que l'ordre d'écrou a été rendu par une autorité incompétente et sans ordre d'arrestation préalable (cf. mémoire p. 3-4 et 10).
3.1. Sauf dans les cas cités expressément à l'art. 95 LTF - non réalisés ici -, la violation du droit cantonal ne constitue pas un motif de recours en tant que tel. La partie recourante peut uniquement se plaindre de ce que l'application du droit cantonal par l'autorité précédente consacre une violation du droit fédéral au sens de l'art. 95 let. a LTF, en particulier qu'elle est arbitraire (<ref-ruling> consid. 2.2 p. 69). Le Tribunal fédéral n'examine le moyen fondé sur la violation d'un droit constitutionnel ou du droit cantonal que si le grief a été invoqué et motivé de manière précise (art. 106 al. 2 LTF). Cette disposition exige que le grief soit exposé de manière claire et détaillée (<ref-ruling> consid. 3 p. 351 s.).
3.2. La cour cantonale a relevé qu'en vertu de l'art. 372 CP, il incombait aux cantons d'exécuter les jugements définitifs et qu'en application de cette disposition et du droit cantonal (art. 5 et 40 LaCP/GE), le Département de la sécurité était l'autorité compétente pour faire exécuter les peines et mettre en oeuvre concrètement les modalités d'exécution (cf. arrêt p. 12 et 13). Elle a spécifié que le SAPEM avait agi sur la base d'un ordre du Chef du Département de la sécurité, dont le SAPEM dépendait, et qu'à l'instar de tout organe subalterne, il était tenu d'y donner suite. Dans ce cadre, l'intervention du SAPEM équivalait à la fois à un ordre d'exécution de la peine pour le 4 octobre 2013 et à un ordre d'arrestation immédiate pour cette même date (cf. arrêt p. 14 et 18).
3.3. Le recourant n'expose pas le contenu des normes cantonales dont il invoque une application arbitraire. Il n'explique pas quel aspect spécifique de ces dispositions serait entaché d'une interprétation insoutenable. Il se contente d'affirmations sans s'efforcer de dire en quoi l'approche cantonale serait arbitraire. La motivation qu'il présente est insuffisante au regard des exigences accrues posées par l'art. 106 al. 2 LTF. Ses critiques sont irrecevables.
4.
Le recourant se plaint d'une violation des art. 5, 9 Cst., et 3 al. 2 let. a CPP. Il relève que dans sa discussion avec le SAPEM à fin septembre 2013, il lui avait été indiqué, conformément à la marge de manoeuvre dont ce service disposait, qu'il entrerait en détention en février 2014 au pénitencier de Witzwil en section ouverte. Son intérêt résidait non seulement dans le fait de passer Noël en famille mais aussi d'intégrer un pénitencier en section ouverte et non Champ-Dollon, qui connaît des conditions drastiques de détention. Il est ainsi d'avis que ce revirement de l'autorité contrevient au principe de la bonne foi.
4.1. Le principe de la bonne foi exige que l'administration et les administrés se comportent réciproquement de manière loyale. En particulier, l'administration doit s'abstenir de tout comportement propre à tromper l'administré. A certaines conditions, le citoyen peut ainsi exiger de l'autorité qu'elle se conforme aux promesses ou assurances qu'elle lui a faites et ne trompe pas la confiance qu'il a légitimement placée dans celles-ci. Cela peut notamment être le cas lorsque l'administration est intervenue à l'égard de l'administré dans une situation concrète et celui-ci doit avoir pris, en se fondant sur les promesses ou le comportement de l'administration, des dispositions qu'il ne saurait modifier sans subir de préjudice (<ref-ruling> consid. 6.1 p. 636 s.; <ref-ruling> consid. 7.1 p. 381).
4.2. La cour cantonale a relevé que le SAPEM avait dans un premier temps, à la suite de l'entretien du 27 septembre 2013, déféré au souhait du recourant de passer Noël en famille puisque ce service avait écrit le 30 du même mois au pénitencier de Witzwil pour réserver "si possible" une place en section ouverte dans l'établissement pour le 10 février 2014. Toutefois, à la suite du décès d'une éducatrice de La Pâquerette, le Chef du Département avait fait réexaminer la situation des personnes condamnées pour des infractions énumérées à l'art. 64 al. 1 et 1 bis CP, dont le recourant, et avait considéré que la peine infligée à celui-ci devait être exécutée sans délai. Procédant à une pesée des intérêts, la cour cantonale a relevé qu'en principe une peine doit être exécutée sans retard et qu'en fixant au 10 février 2014 l'exécution de la peine de six ans devenue exécutoire le 8 juillet 2013 avec l'arrêt du Tribunal fédéral, le SAPEM avait déjà ajourné le début d'exécution sans véritable motif, le souhait de passer Noël en famille n'en constituant pas un. Il existait en outre dans le contexte de l'époque un intérêt public, à la suite du tragique meurtre de l'assistante sociale, à ce que la peine soit exécutée sans délai. La cour cantonale a ainsi exclu une violation du principe de la bonne foi.
4.3. Le recourant a été condamné à une peine importante (six ans) pour des graves infractions contre l'intégrité sexuelle (viol, contrainte sexuelle, actes d'ordre sexuel avec des enfants). De manière générale, les peines doivent être exécutées sans retard (cf. MICHEL PERRIN, in Commentaire romand, Code de procédure pénale suisse, 2011, n° 15 ad art. 439 CPP). Cette exigence se justifie d'autant plus à l'égard d'une peine importante pour des infractions graves en considération de la crédibilité du système pénitentiaire et de l'effectivité des sanctions. En l'espèce, le recourant a déjà bénéficié de quelques mois après le prononcé de l'arrêt du Tribunal fédéral le 8 juillet 2013, à partir duquel sa condamnation était exécutoire. De plus, compte tenu du drame de l'assistante sociale tuée dans le cadre d'une sortie avec un détenu, il existait un intérêt public indéniable à ce que toute personne, à l'instar du recourant, condamnée pour une infraction grave à une peine importante, soit incarcérée. Dans ces conditions, le recourant ne saurait exiger le maintien de la position initiale du SAPEM dans le cadre de l'entretien du 27 septembre 2013. On ne perçoit pas non plus quel préjudice il subirait dès lors que son placement à Champ-Dollon a un caractère temporaire en attendant son transfert dans un autre établissement selon les indications de la cour cantonale (cf. arrêt p. 21). Le recourant ne formule aucun grief recevable à cet égard (cf. infra consid. 6). Le SAPEM n'avait pas non plus garanti un placement en section ouverte, l'indication "si possible" étant apposée dans sa demande au pénitencier de Witzwil. Cet aspect des conditions de détention était ainsi encore incertain. En définitive, il n'existe aucune violation du principe de la bonne foi.
5.
Le recourant considère que les conditions d'application de l'art. 439 al. 3 CPP n'étaient pas réalisées. Il invoque aussi une violation de l'art. 439 al. 4 CPP (et 208 CPP).
5.1. L'art 439 CPP prévoit que la Confédération et les cantons désignent les autorités compétentes pour l'exécution des peines et des mesures et règlent la procédure; les réglementations spéciales prévues par le présent code et par le CP sont réservées (al. 1). L'autorité d'exécution édicte un ordre d'exécution de peine (al. 2). Les décisions entrées en force fixant des peines et des mesures privatives de liberté sont exécutées immédiatement dans les cas suivants: a. il y a danger de fuite; b. il y a mise en péril grave du public; c. le but de la mesure ne peut pas être atteint d'une autre manière (al. 3). Pour mener à bien l'ordre d'exécution de la peine, l'autorité d'exécution peut arrêter le condamné, lancer un avis de recherche à son encontre ou demander son extradition (al. 4).
5.2. La cour cantonale a considéré que l'art. 439 al. 3 CPP ne s'appliquait pas en l'espèce dès lors que la détention n'avait pas été exécutée immédiatement mais différée puisque la condamnation était exécutoire le 8 juillet 2013 avec l'arrêt du Tribunal fédéral et que l'exécution n'avait eu lieu qu'à partir du 4 octobre 2013 (cf. arrêt p. 17). Cette approche est correcte. L'art. 439 al. 3 CPP s'applique à des situations particulières (danger de fuite, mise en péril grave du public) justifiant une exécution immédiate. Si l'exécution n'est pas immédiate, à l'instar du cas d'espèce, alors ce sont les règles cantonales ou celles fédérales réservées par l'art. 439 al. 1 CPP qui s'appliquent pour l'exécution (cf. aussi supra consid. 3.2). Il s'ensuit que c'est en vain que le recourant invoque une violation de l'art. 439 al. 3 CPP, inapplicable ici. Il est vrai que la cour cantonale a exposé une argumentation subsidiaire, pour le cas où cette disposition s'appliquerait (arrêt p. 17 4 e §). Cela n'étant pas le cas, cette argumentation est sans portée.
5.3. Selon sa teneur, l'art. 439 al. 4 CPP se réfère à l'ordre d'exécution prévu par l'al. 2. Il apparaît ainsi que l'application de l'art. 439 al. 4 CPP n'est pas réservée à la situation visée par l'art. 439 al. 3 CPP, mais concerne au contraire tout ordre d'exécution de peine (cf. PERRIN, op. cit., nos 21 ss ad art. 439 CPP). La critique du recourant est ainsi infondée. Il est par ailleurs admis que l'art. 208 CPP, qui définit la forme du mandat d'amener, s'applique par analogie pour l'arrestation prévue à l'art. 439 al. 4 CPP (cf. NIKLAUS SCHMID, Schweizerische Strafprozessordnung, Praxiskommentar, 2 e éd. 2013, n° 10 ad art. 439 CPP). La cour cantonale a relevé que le recourant avait été arrêté en vertu d'une décision écrite du SAPEM sous la forme d'un ordre d'écrou du 4 octobre 2013. Elle a expliqué pourquoi ce document respectait les exigences de forme requises (cf. arrêt p. 19 et 20). Le recourant se contente d'émettre une dénégation sans s'en prendre à la motivation cantonale. Son grief est sur ce point irrecevable.
5.4. Le recourant soutient que son arrestation en vertu de l'art. 439 al. 4 CPP contreviendrait au principe de la proportionnalité. Dans ce cadre, il persiste à contester le champ d'application de l'art. 439 al. 4 CPP. Il est renvoyé à ce qui est dit ci-dessus (supra, consid. 5.3). Pour le reste, le recourant cherche à mettre en cause les motifs de sa mise en détention. Il ne formule cependant aucun grief recevable ou différent de ceux déjà traités (supra consid. 3.3 et 4.3). Cela étant, le principe de la proportionnalité ne saurait avoir été violé pour la raison que l'arrestation a été accomplie par la police. L'affirmation du recourant selon laquelle il aurait donné suite à une convocation est une pure conjecture, inapte à justifier l'admission de son grief.
6.
Le recourant se prévaut d'une violation de l'art. 1 du règlement genevois sur le régime intérieur de la prison et le statut des personnes incarcérées (RRIP/GE; RSG F 1 50.04). Selon lui, la prison de Champ-Dollon est réservée aux personnes en détention préventive, voire aux condamnés à une peine privative de liberté jusqu'à trois mois. Sa situation n'entrerait pas dans les cas exceptionnels réservés par l'art. 1 al. 3 let. b RRIP/GE.
L'art. 1 al. 1 et 2 RRIP/GE spécifie que la prison de Champ-Dollon est en particulier réservée aux prévenus en détention préventive ou en exécution de peine jusqu'à trois mois. Cependant, l'al. 3 let. b de cette disposition prévoit que Champ-Dollon peut exceptionnellement accueillir des condamnés autres que les personnes mentionnées à l'al. 1 et 2. La cour cantonale a indiqué qu'en raison du caractère éminemment temporaire du placement du recourant à Champ-Dollon, dans l'attente d'un transfert dans un autre pénitencier, la détention à Champ-Dollon était exceptionnellement justifiée au sens de l'art. 1 al. 3 let. b RRIP/GE (arrêt p. 21). Le recourant se limite à affirmer que sa situation n'est pas exceptionnelle et qu'elle n'est pas éminemment temporaire au regard des délais d'attente pour entrer en pénitencier. Une telle motivation est non seulement insuffisante au regard des exigences de l'art. 106 al. 2 LTF (cf. supra consid. 3.1) mais se base sur des faits non constatés (longueur des délais d'attente), ce qui n'est pas admissible (cf. art. 105 al. 1 LTF). Les critiques sont irrecevables.
7.
En conclusion, le recours doit être rejeté dans la mesure où il est recevable. Le recourant supporte les frais judiciaires (art. 66 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties et à la Chambre pénale de recours de la Cour de justice de la République et canton de Genève.
Lausanne, le 1er avril 2014
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet