This was good for me because I hadn't been aware of the Nadeau & Bengio paper, which is actually very interesting. It's a difficult paper and I can't guarantee that my understanding of it is 100% correct, so whatever I write now about that paper doesn't come with any guarantee. As interesting as the paper is, I don't think it's written in the most clear manner, see below.
(1) What is important here is about what "population of problems" you want to make general statements. If you just want to see which method is doing how much better in your experiments, you don't need a test; you can just look at the difference between means and visual displays.
(2) Now obviously there is some random variation in this, and testing is about asking whether the differences that you see can maybe be explained by random variation, but you have to decide what kind variation is relevant. I gather that you only have a single dataset. Now one perspective (P1 from now) would be that you say the dataset is fixed, and you only are interested in making statements about random variation over the random splits. Another perspective (P2) is that you also take into account that the dataset is random, and you want to make statements about the underlying population $P$ of datasets. My first comment here is that P2 seems at first glance hopeless; you only have a single dataset, that is, you have an effective sample size of one of datasets from that population. From sample size one not much can be said.
(3) I'll discuss P2, the Nadeau and Bengio paper and the issue of generalising to $P$ in (6). This is subtle and difficult, and I first make some simpler statements.
(4) Under P1, different splits of the data are in fact independent (they are not under P2, which is where the difficulty in Nadeau and Bengio comes from), so a standard paired t-test should be fine here assuming that your number of replicates is large enough, and 100 should do. But obviously this only allows you to generalise to what is expected to happen with more splits on the same dataset (I actually think that's the best you'll get, see below).
(5) The question whether you choose a one- or two-sided test depends on whether your initial question is asymmetric or symmetric. If you are only interested in whether method A is better (because that's the new one, and if it isn't better, you will throw it away regardless of whether it's worse or whether they are the same), you use a one-sided test. If you are interested whether there is any evidence that on this dataset the methods are different in any direction, you use a two-sided test.
(6) It actually seems that P2 is what Nadeau and Bengio address in their paper; in all their modelling the dataset is treated as random, and it looks like they are going for a generalisation error that can be estimated from having a single dataset, but their paper doesn't make that terribly clear. Actually, in their simulation study, they generate 1000 datasets, however they note on p.259 that the methods in Sec. 4 (of which you have cited one) apply to a single dataset. So Nadeau and Bengio treat a setup of which I intuitively say that this is a "effective sample size one" situation in which you really can't say that much. Am I saying they are wrong in doing this? Well, it depends. If you assume that your dataset $Z=(Z_1,\ldots,Z_n)$ is i.i.d., and also randomly drawn from a population $P$ of such datasets (meaning that not only the data in $Z$ are i.i.d., but also that different full datasets $Z$ would be i.i.d. if more than one was drawn), actually $Z$ does contain quite a bit of information, if $n$ is large enough, about the expected variation in $P$. So the computations in Nadeau and Bengio are legitimate (and in their simulation they obviously treat such cases, so they do exist), however I think that in practice they are of quite limited relevance. This is because usually if you only have a single dataset, it is very hard to make the case that this is drawn i.i.d. from any well defined population. That $P$ is fictional; it is "let's imagine there is a population that is represented in i.i.d. manner by this dataset", which basically means that the dataset implicitly defines the population and ultimately you are still only making inferences about the dataset itself. (I do not exclude the possibility that there are situations in which a more convincing case in favour of the applicability of that theory can be made, but I think they are very exceptional at best.)
Reading the paper we can also realise that Nadeau and Bengio use some approximations that they sound very cautious about, and that are not based on mathematical proofs of validity. The validity would actually depend on the precise nature of $P$, about which the authors don't make assumptions (which in any case could never be checked with an effective sample size of 1). My understanding is that the imprecisions in this paper (about which the authors are laudably open) come exactly from the fact that for saying anything precise they'd need bold assumptions about $P$ that are not testable in any real situation, unless you have substabtially more than one dataset. As far as the methods they propose do well in their simulations, this is due to the fact that simulation setups have been chosen that play out reasonably nicely, on top of the fact that obviously in their simulations the $Z$ is in fact i.i.d. drawn from $P$, which is the key assumption that they in fact make. In most real situations, if you have one real dataset $Z$ and try to apply these methods, the very fact that this is the one dataset you have already means that it is special in some way and has not been randomly i.i.d. drawn from any well defined population of datasets! (Otherwise why would it be a problem to draw more?)
So my impression is, the methodoloy of Nadeau and Bengio will not get you much further than a simple paired t-test; and you can only reliably generalise to what would happen with more splits on the very same dataset. If you want more, you need more (truly independent) datasets.