Why is this script so slow?
There are a few things to improve in your scripts.

for v in [v for v in bm.verts if v.select]:


Here you create a list of selected vertices, and then loop over that list. That list constructed using the list comprehension is unnecessary. Instead just write this:

for v in bm.verts:
    if not v.select:
        continue
    ...


The same goes for creating Empties in your second script. It's not necessary to first create the entire list in memory. Either use a generator expression or just use an if ...: continue construct.



The empties.append((v.index, empty)) adds items to a list that is never used. Better remove it.



In the second script you use operators where you could use regular functions. For example, use bpy.data.armatures.new(...) and link it to a new object, instead of using bpy.ops.object.armature_add(...). Every operator call creates an undo-step in memory, so it's much slower than using direct data access functions.

Here is the second script, which uses a single armature for all the bones, and as much direct data access (properties, function calls) as possible:

import bpy

C = bpy.context
try:
    arm_ob = bpy.data.objects['Armature']
except KeyError:
    arm = bpy.data.armatures.new('Armature')
    arm_ob = bpy.data.objects.new('Armature', arm)
    C.scene.objects.link(arm_ob)
else:
    arm = arm_ob.data

# Set to EDIT mode so we can add bones.
C.scene.objects.active = arm_ob
bpy.ops.object.mode_set(mode='EDIT')

# Add the bones
for l in C.scene.objects:
    if l.type != 'EMPTY':
        continue

    bone = arm.edit_bones.new(l.name)
    bone.head = l.location
    bone.tail = bone.head
    bone.tail.z += 0.5

# Go to POSE mode so we can add constraints
bpy.ops.object.mode_set(mode='POSE')
for bone in arm_ob.pose.bones:
    clc = bone.constraints.new('COPY_LOCATION')
    clc.target = C.scene.objects[bone.name]


The armature for the subdivided Suzanne below took around a second to create, and consists of 2012 bones: