Finding many paths in a graph
There's no docstring. What does travel do? What arguments does it take? What does it return?
The meaning of the data structure queue is far from clear. It seems to be a deque whose elements represent paths, each path being represented by a list of pairs (v, e) where v is the vertex on the path, and e is None if this is the first vertex on the path, or an iterable of edges by which v could be reached from the previous vertex of the path. This kind of complex data structure is hard to understand, and would be clearer if it had its own class, for example using collections.namedtuple.
It would be a good idea to generate the paths one at a time using the yield statement, so that if a consumer is processing the paths one at a time then the whole list of paths does not have to be stored in memory.
Generating the paths would also allow us to omit the count argument and keep generating paths forever. If the caller wants at most 1000 paths, they can use itertools.islice:

islice(travel(graph, start, dests), 1000)

The test if at in dests: takes time proportional to the number of destinations. This would run in constant time if dests were converted to a set.
It would be reasonable to insist on the graph having a key for every vertex (whose corresponding value is an empty dictionary if the vertex is a sink); this would allow you to write graph[at] instead of graph.get(at, {}) which creates and throws away an empty dictionary.
The implementation stores path + [item] in the queue, taking time and space proportional to the length of the path, on each iteration. This is unnecessary: many paths will share the same initial prefix, so a data structure which stored only the last item on the path, together with a reference to the previous data structure on the path, would take constant time on each iteration. The whole path could be reconstructed when the destination is reached by following the references.


2. Revised code

from collections import deque, namedtuple

# Node in the breadth-first search with fields:
# vertex -- the current vertex in the search
# edges -- iterable of edges from previous vertex (or None)
# prev -- previous Search node (or None)
SearchNode = namedtuple('SearchNode', 'vertex edges prev')

def travel(graph, start, dests):
    """Generate paths in graph beginning at the vertex start and ending at
    any of the vertices in dests.

    The graph must be represented as a mapping from vertex to a
    mapping from neighbouring vertex to an iterable of edges.

    """
    dests = set(dests)
    queue = deque([SearchNode(start, None, None)])
    while queue:
        at = queue.popleft()
        if at.vertex in dests:
            edges = []
            prev = at
            while prev.edges is not None:
                edges.append(prev.edges)
                prev = prev.prev
            for path in product(*reversed(edges)):
                yield ''.join(path)
        for v, e in graph[at.vertex].items():
            queue.append(SearchNode(v, e, at))