They are not lost. They will either go through eventually (most probably, but it may take anywhere from several minutes to several days), or they will be once again accessible from the original paper wallet once the network forgets about the transaction.
Of course, if you disposed of the original paper wallet and don't have a backup of that private key, then they could become lost if the transaction gets dropped from the memory pool before it gets confirmed.
Perhaps it would be a good idea to make a copy of the raw transaction so that you can re-broadcast it if needed.