An NFA (with $\epsilon$-moves or not) can be viewed naturally as a directed multi-graph. We will use "state" and "node" interchangeably.
Whether an NFA accepts an infinite language is the same as whether there is a path from the initial state to an accepting state that contains at least one state that is a part of a cycle. Here we consider a self-loop as a cycle. See Yuval's answer for a simple proof.
An algorithm in polynomial time
A DFS from the initial state can determine all states that are reachable from the initial state.
A DFS from each state can determine whether the NFA can reach an accepting state from that state.
For each state, we can use a depth-first-search (DFS) to determine whether it is a part of a cycle.
If there is a state which is reachable from the initial state and from which the NFA can reach an accepting state and which is a part of a cycle, the answer is Yes. Otherwise, the answer is No.
An algorithm in linear time
For every ordered nodes $s_1$ and $s_2$ in the directed multi-graph, we can replace all edges from $s_1$ to $s_2$ by a single edge from $s_1$ to $s_2$, which transforms the directed multi-graph into a directed graph without multi-edges (with self-loops possibly). This transformation does not affect paths nor cycles.
Call the transformed graph $H$.
A DFS on $H$ from the initial state can mark all reachable accepting states. Another DFS on $H$ starting from an additional node, "the super-accepting state" that is connected from all accepting states, treating each edge backwards, can mark all states from which the NFA can reach an accepting state. A state is marked by both DFS iff there is a path from the initial state to an accepting state that contains that state.
A state is a part of a cycle iff it is a part of a cyclic strongly connected components (SCCs). An SCC is called cyclic if it contains a cycle, i.e., if it contains either a self-loop or more than one node. We can adapt easily any one of common linear-time algorithms that find all SCCs to find all cyclic SCCs with the same time-complexity.
If there is a state that is marked by both DFS and is part of a cyclic SCC, the answer is Yes. Otherwise the answer is No.
Since each of the transformation, both DFSs, the adapted SCC-finding algorithm and the final check runs in linear time, the entire algorithm runs in linear time.