Retrieving HKLM nodes of Windows10 Registry
It looks to me, one of your biggest problems is working directly with the Nodes of the TreeView.  This necessitates calling Paint() everytime you add a node.  If you start with a new TreeNode as root, and build the tree on that, you can add the whole thing to the TreeView by adding the root to the Nodes.  

I also found that running VS as administrator greatly reduced the number of errors, which also sped it up.

By using a custom TreeNode class that inherits from Forms.TreeNode, you can recursively fill the tree inside the class.  This also allows you to store the actual RegistryKey object in each node.  Here's a relatively simple way of doing it:

Public Class RegistryTreeNode
    Inherits TreeNode
    Private Class SecurityExceptionLogger
        Private Shared Property Exceptions As New List(Of (String, SecurityException))
        Private Shared TempFileName As String = Path.GetTempFileName()
        Private Shared writer As StreamWriter
        Private Shared reader As StreamReader
        Public Shared Async Sub Add(exception As SecurityException)
            Exceptions.Add((Now.ToUniversalTime, exception))
            Using writer = New StreamWriter(TempFileName, True)
                Await writer.WriteLineAsync($"{Now.ToUniversalTime} - {exception.Message}")
            End Using
        End Sub
        Public Shared Sub PrintExceptions(stream As StreamWriter)
            Using stream
                Exceptions.ForEach(Async Sub(x)
                                       Await stream.WriteLineAsync($"{x.Item1} - {x.Item2.Message}")
                                   End Sub)
            End Using
        End Sub

    End Class
    Private _RegKey As RegistryKey

    Private Property RegKey As RegistryKey
        Get
            Return _RegKey
        End Get
        Set
            _RegKey = Value
            Name = _RegKey.Name
            Text = Name
            For Each key In _RegKey.GetSubKeyNames
                Try
                    Nodes.Add(New RegistryTreeNode(_RegKey.OpenSubKey(key)))
                Catch ex As SecurityException
                    SecurityExceptionLogger.Add(ex)
                Catch ex As Exception
                    MsgBox(ex.Message)
                End Try
            Next
        End Set
    End Property

    Public Sub New()
        MyBase.New()
        RegKey = Registry.LocalMachine
    End Sub
    Public Sub New(newRegistryKey As RegistryKey)
        MyBase.New()
        RegKey = newRegistryKey
    End Sub
End Class


I hardcoded the default key to Registry.LocalMachine for your uses.  Simply Dim root = New RegistryTreeNode() and the whole tree will build itself.

You'll notice I made a simple logger that writes to file as well as keeping a record in memory, instead of just in memory, just as an exercise.

Another way to speed things up, is to only load the first sub level of nodes on start up.  You can then use the AfterSelect event handler to load the sub nodes of the key you want to expand.  Something like this:

Public Class Form1
    Dim root = New RegistryTreeNode(Registry.LocalMachine)
    Public Sub New()

        ' This call is required by the designer.
        InitializeComponent()

        ' Add any initialization after the InitializeComponent() call.
        TreeView1.Nodes.Add(root)
    End Sub


    Private Sub TreeView1_AfterSelect(sender As Object, e As TreeViewEventArgs) Handles TreeView1.AfterSelect
        Dim node = DirectCast(TreeView1.SelectedNode, RegistryTreeNode)
        For Each key In node.GetSubKeyNames
            Try
                Dim regKey = New RegistryTreeNode(node.OpenSubKey(key))
                If Not regKey Is Nothing Then
                    node.Nodes.Add(regKey)
                End If

            Catch ex As SecurityException
                SecurityExceptionLogger.Add(ex)
            Catch ex As Exception
                MsgBox(ex.Message)
            End Try
        Next

    End Sub

End Class
Class SecurityExceptionLogger
    Private Shared Property Exceptions As New List(Of (String, SecurityException))
    Private Shared TempFileName As String = Path.GetTempFileName()
    Private Shared writer As StreamWriter
    Private Shared reader As StreamReader
    Public Shared Async Sub Add(exception As SecurityException)
        Exceptions.Add((Now.ToUniversalTime, exception))
        Using writer = New StreamWriter(TempFileName, True)
            Await writer.WriteLineAsync($"{Now.ToUniversalTime} - {exception.Message}")
        End Using
    End Sub
    Public Shared Sub PrintExceptions(stream As StreamWriter)
        Using stream
            Exceptions.ForEach(Async Sub(x)
                                   Await stream.WriteLineAsync($"{x.Item1} - {x.Item2.Message}")
                               End Sub)
        End Using
    End Sub

End Class
Public Class RegistryTreeNode
    Inherits TreeNode

    Private _RegKey As RegistryKey

    Private Property RegKey As RegistryKey
        Get
            Return _RegKey
        End Get
        Set
            _RegKey = Value
            Name = _RegKey.Name
            Text = Name.Substring(Name.LastIndexOf("\"c) + 1)

        End Set
    End Property

    Public Sub New()
        MyBase.New()
        RegKey = Registry.LocalMachine
    End Sub
    Public Sub New(newRegistryKey As RegistryKey)
        MyBase.New()
        RegKey = newRegistryKey
    End Sub
    Public Function GetValueNames() As List(Of String)
        Return _RegKey.GetValueNames().ToList()
    End Function
    Public Function GetValueKind(name As String) As RegistryValueKind
        Return _RegKey.GetValueKind(name)
    End Function
    Public Function GetValue(name As String) As Object
        Return _RegKey.GetValue(name)
    End Function
    Public Function GetSubKeyNames() As String()
        Return _RegKey.GetSubKeyNames()
    End Function
    Public Function OpenSubKey(key As String) As RegistryKey
        Return _RegKey.OpenSubKey(key)
    End Function
End Class


I moved the SecurityExceptionLogger outside the RegistryTreeNode class.  You can also load the values for the keys, if needed, by looping through them after the sub nodes are added.