Paginate An Array Of Entries
As Victor rightfully points out, the {% paginate %} tags require an ElementCriteriaModel, so you can't do what you're doing in your first example because as soon as you call:

{% for databyte in allDatabytes %}


Craft hits the database and converts the ElementCriteriaModel into actual EntryModels.

We also don't have support, yet, for passing :empty: into things like AssetFields, TagFields, etc., which is why your second example won't work...  however that is on our list to add!

In this case, I think your best bet is going to be to do through the search service with something like this:

{# Search for 10 entries in the 'databytes' section where the 'series' assetField doesn't have anything selected. #}
{% set myCriteria = craft.entries.section('databytes').search('-series:*').limit(10) %}

{% paginate myCriteria as entries %}
    {% for entry in entries %}
        {{ entry.title }}
    {% endfor %}

    {% if paginate.prevUrl %}
        &lt;a href="{{ paginate.prevUrl }}"&gt;Previous Page&lt;/a&gt;
    {% endif %}

    {% if paginate.nextUrl %}
        &lt;a href="{{ paginate.nextUrl }}"&gt;Next Page&lt;/a&gt;
    {% endif %}
{% endpaginate %}