My name is Abdul Rahman, I want to change it to Abdur-Rahman as this is the way it is supposed to be pronounced in Arabic. Would this be permissible if I did?
It is permissible to change your name, long as you are changing your name to one that is acceptable in Islam. In your case, it is permissible since you are correcting the spelling to match the more proper pronunciation.
Names may be changed when the original name is not a good name ('Asiya means "disobeyer"):
عَنِ ابْنِ عُمَرَ، أَنَّ ابْنَةً لِعُمَرَ، كَانَتْ يُقَالُ لَهَا عَاصِيَةُ فَسَمَّاهَا رَسُولُ اللَّهِ صلى الله عليه وسلم جَمِيلَةَ
Ibn 'Umar reported that 'Umar had a daughter who was called 'Asiya. Allah's Messenger (ﷺ) gave her the name of Jamila.
Names may also be changed from a good name to another good name as in the case of Barra to Zainab:
حَدَّثَتْنِي زَيْنَبُ، بِنْتُ أُمِّ سَلَمَةَ قَالَتْ كَانَ اسْمِي بَرَّةَ فَسَمَّانِي رَسُولُ اللَّهِ صلى الله عليه وسلم زَيْنَبَ. قَالَتْ وَدَخَلَتْ عَلَيْهِ زَيْنَبُ بِنْتُ جَحْشٍ وَاسْمُهَا بَرَّةُ فَسَمَّاهَا زَيْنَبَ
Zainab, daughter of Umm Salama, reported: My name first was Barra. Allah's Messenger (ﷺ) gave me the name of Zainab. Then there entered (into the house of Allah's Prophet as a wife) Zainab, daughter of Jahsh, and her name was also Barra, and he gave her the name of Zainab.
Zainab's name was changed by the Prophet ﷺ as he did with another companion, Safīna, as in this hadith:
سَأَلْتُ سَفِينَةَ عَنِ اسْمِهِ، فَقَالَ: إِنِّي مُخْبِرُكَ بِاسْمِي، سَمَّانِي رَسُولُ اللهِ صَلَّى اللهُ عَلَيْهِ وَسَلَّمَ سَفِينَةَ، قُلْتُ: لِمَ سَمَّاكَ سَفِينَةَ؟ قَالَ: خَرَجَ وَمَعَهُ أَصْحَابُهُ فَثَقُلَ عَلَيْهِمْ مَتَاعُهُمْ فَقَالَ: «ابْسُطْ كِسَاءَكَ»، فَبَسَطْتُهُ فَجَعَلَ فِيهِ مَتَاعَهُمْ ثُمَّ حَمَلَهُ عَلَيَّ فَقَالَ: «احْمِلْ مَا أَنْتَ إِلَّا سَفِينَةٌ»، قَالَ: فَلَوْ حَمَلْتُ يَوْمَئِذٍ وِقْرَ بَعِيرٍ أَوْ بَعِيرَيْنِ أَوْ خَمْسَةٍ أَوْ سِتَّةٍ مَا ثَقُلَ عَلَيَّ
— NOTE: My own translation, so treat with care:
I asked Safīna about his name, and he said: "I will inform you about my name. The Messenger of Allah ﷺ gave me the name Safīna." I asked him: "Why did he call you Safīna?" He said: "He went with his companions on a trip; they found their belongings to be too heavy. He [the Prophet] said: 'Spread your garment', and so I did. He put their belongings in it, then he carried it and put it on me. He [the Prophet] said: 'Carry for you are a ship [safīna].' That day, if I was given a load of a camel or two camels or five or six, I would have been able to."